Non-Regular Language, Pumping Lemma

  • Thread starter Fatima Hasan
  • Start date
  • Tags
    Language
In summary, a non-regular language is a type of language that cannot be recognized by a finite state machine, and the Pumping Lemma is a theorem used to prove that a language is non-regular by showing that it cannot be pumped in a way that satisfies the conditions of the lemma. This lemma cannot be used to prove that a language is regular, and it has applications in theoretical computer science, natural language processing, and cryptography.
  • #1
Fatima Hasan
319
14

Homework Statement


Prove that ## L ## is non-regular language.
png.png


2. Homework Equations

none

The Attempt at a Solution


upload_2018-4-20_18-13-24.png


upload_2018-4-20_18-13-33.png


upload_2018-4-20_18-13-40.png


upload_2018-4-20_18-13-52.png


So L is non-regular !
Is my solution correct?
 

Attachments

  • upload_2018-4-20_18-13-24.png
    upload_2018-4-20_18-13-24.png
    12.8 KB · Views: 1,267
  • upload_2018-4-20_18-13-33.png
    upload_2018-4-20_18-13-33.png
    11.8 KB · Views: 1,553
  • upload_2018-4-20_18-13-40.png
    upload_2018-4-20_18-13-40.png
    12.2 KB · Views: 966
  • upload_2018-4-20_18-13-52.png
    upload_2018-4-20_18-13-52.png
    12.7 KB · Views: 1,057
  • png.png
    png.png
    1.6 KB · Views: 927
Physics news on Phys.org
  • #2
Fatima Hasan said:

Homework Statement


Prove that ## L ## is non-regular language.
View attachment 224379

2. Homework Equations

none

The Attempt at a Solution


View attachment 224375

View attachment 224376

View attachment 224377

View attachment 224378

So L is non-regular !
Is my solution correct?
It does appear to be correct. You could simplify it a little by noting that you only need one counter-example to prove a statement false.
Edit: I take that back. I think you are correct to consider all of the cases, since the pumping lemma says a way to divide S into xyz that satisfies the rest of the conditions exists.
 
  • Like
Likes Fatima Hasan

Related to Non-Regular Language, Pumping Lemma

1. What is a non-regular language?

A non-regular language is a type of language that cannot be recognized by a finite state machine, also known as a regular grammar. These languages often have complex or infinite patterns that cannot be represented by a finite number of states.

2. What is the Pumping Lemma?

The Pumping Lemma is a theorem in formal language theory that states that any regular language can be "pumped" or repeated an infinite number of times while still remaining a regular language. This lemma is often used as a proof technique to show that a language is not regular.

3. How is the Pumping Lemma used to prove a language is non-regular?

The Pumping Lemma is used to prove a language is non-regular by assuming the language is regular and then showing that the lemma does not hold for that language. This is done by selecting a string from the language that is longer than the number of states in the finite state machine, and then showing that it cannot be pumped in a way that satisfies the conditions of the lemma.

4. Can the Pumping Lemma be used to prove that a language is regular?

No, the Pumping Lemma can only be used to prove that a language is non-regular. It cannot be used to prove that a language is regular because there are many regular languages for which the lemma does not hold. Therefore, if the lemma does not hold for a language, it does not necessarily mean that the language is regular.

5. What are some real-world applications of the Pumping Lemma?

The Pumping Lemma is primarily used in theoretical computer science to prove properties of formal languages. However, it can also be applied in areas such as natural language processing, where it can help identify patterns and structures in human languages. Additionally, the Pumping Lemma has been used in cryptography to analyze the security of certain encryption schemes.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
5
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Back
Top