Show that languages are regular

  • Thread starter evinda
  • Start date
  • Tags
    Regular
In summary, to show that languages are regular, we can use the lemma that states if the language of an automaton has an infinite number of words, there are specific words that are contained in the language. Using this lemma, we can prove that the languages L={ww^{R}:w ε {a,b}*} and L={ww:w ε {a,b}*} are not regular. For subquestion b, we cannot use the original version of the Pumping Lemma because the words written backwards are not considered. However, for subquestion a, we can use the word 0^{p}10^{p}1, where p is the pumping length, and show that the second word has an even number of b's,
  • #1
evinda
Gold Member
MHB
3,836
0
Show that languages are regular!

Homework Statement


Use the lemma:
<<If the language L(A) of an automaton A has an infinite number of words,then there are words a,m,t ε Σ*,so that |at|≤|Σ_{k}|,and each word a m^{i}t,i≥0 is contained in L(A) >>(version of Pumping Lemma)and show that the following languages are not regular:
a) L={ww^{R}:w ε {a,b}*} (w^{R}=the word w is written backwards)
b)L={ww:w ε {a,b}*}

P.S: Σ_{k} is the set of states.

2. The attempt at a solution

For the subquestion b,if we would have the original version of Pumping Lemma,we could take the word 0^{p}10^{p}1,where p is the pumping length.Can we also do this in our case?
 
Physics news on Phys.org
  • #2
I don't think so,because the words that are written backwards are not taken in consideration.For the subquestion a,we can take the word 0^{p}10^{p}1,where p is the pumping length.Then,we get the following two words:a) 0^{p}10^{p}1b) 0^{p+1}10^{p-1}1Now,the first word is contained in L(A),but the second one is not,because it has an even number of b's.Therefore,the language is not regular.
 

Related to Show that languages are regular

1. What is a regular language?

A regular language is a type of formal language that can be generated by a regular expression or recognized by a deterministic finite automaton (DFA). It is a subset of the larger class of formal languages and is characterized by its ability to be recognized by a finite state machine.

2. How can we prove that a language is regular?

To prove that a language is regular, we can use the pumping lemma. This lemma states that if a language is regular, then there exists a finite pumping length n, such that any string in the language with a length greater than n can be pumped (repeated) to generate other strings in the same language. If we can successfully demonstrate this for a language, then we can conclude that it is regular.

3. What are some common examples of regular languages?

Some common examples of regular languages include regular expressions, which are used for pattern matching in programming languages, and simple arithmetic expressions, such as addition and multiplication of single-digit numbers. Additionally, most programming languages are considered regular languages due to their well-defined syntax and structure.

4. How are regular languages different from other types of formal languages?

Regular languages are unique in that they can be recognized and generated by a finite state machine. Other types of formal languages, such as context-free languages, require more complex machines, such as pushdown automata, to recognize and generate them. Regular languages are also limited in their ability to handle nested structures and are therefore not as powerful as other types of formal languages.

5. Why is it important to show that a language is regular?

Proving that a language is regular is important because it allows us to determine the complexity of the language and the type of automaton needed to recognize and generate it. This information is crucial for designing efficient algorithms and programming languages, as well as for analyzing the computational power of different machines and languages.

Similar threads

  • 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
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
669
  • 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
1
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
7
Views
1K
Replies
1
Views
961
Back
Top