Question

Are the following languages over {a, b} regular? If they are then prove it. If they...

Are the following languages over {a, b} regular? If they are then prove it. If they are not prove it with the Pumping Lemma

  1. {an bm | m != n, n >= 0}
  2. {w | w contains the substring ‘aaa’ once and only once }

Clear concise details please, if the language is regular, provide a DFA/NFA along with the regular expression. Thank you. Will +1

Homework Answers

Answer #1

Answer a) The given Language is not regular , here are some proof

proof1) using pumping lemma

Let ? be the constant in the pumping lemma, and consider the word ????+?!∈?apbp+p!∈L. According to the pumping lemma, it can be decomposes as ???xyz, where |??|≤?|xy|≤p, ?≠?y≠ϵ, and ????∈?xyiz∈L for all ?≥0i≥0. Since |??|≤?|xy|≤p, we must have ?=??y=aq for some ?≤?q≤p; since ?≠?y≠ϵ, we must have ?≥1q≥1. Let ?=?!/?+1i=p!/q+1. Then you can check that ????=??+?!??+?!∉?xyiz=ap+p!bp+p!∉L, contradicting the pumping lemma.

proof 2) by contradiction

Here are two more proofs. The first uses closure properties. If ?L were regular then so would the following language be: ?∗?∗∖?={????:?=?}a∗b∗∖L={anbm:n=m}. However, this language is known to be non-regular.

proof 3)

Another proof uses Myhill–Nerode theory. Let us say that two words ?,?x,y are incomparable if there exists a word ?z such that ??∈?xz∈L but ??∉?yz∉L, or vice versa. In any DFA for ?L, we must have ?(?0,?)≠?(?0,?)δ(q0,x)≠δ(q0,y) (why?). Therefore, if we can find an infinite collection of pairwise incomparable words, then the language is not regular (why?). In the case of ?L, such a collection consists of the words ??ai for all ?≥0i≥0. Indeed, if ?≠?i≠j then ????∈?aibj∈L whereas ????∉?ajbj∉L, showing that ??,??ai,aj are incomparable.

Answer b) yes ,given language is regular there exit the following DFA with th langiage given which shows the language is regular since we can construct a finite automata out of the given language

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Prove that the following languages are not regular using pumping lemma: (a) {w : w !=...
Prove that the following languages are not regular using pumping lemma: (a) {w : w != wR} (b) {ai bjak : k ≤ i + j}
Use the pumping lemma to show that the following languages are not regular. b. A2 =...
Use the pumping lemma to show that the following languages are not regular. b. A2 = {www| w € {a, b}*}
prove that the language L over {c,d,e} is not context free. (using pumping lemma for context...
prove that the language L over {c,d,e} is not context free. (using pumping lemma for context free languages) L= {w ∈ {c,d,e}* : number of c's, number of d's, and number of e's have a common factor greater than 1}
Which one of the following languages over the alphabet {0,1} is described by the regular expression...
Which one of the following languages over the alphabet {0,1} is described by the regular expression (0+1)* 0 (0+1)* 0 (0+1)* ? a.The set of all strings that begin and end with either 0 or 1 b.The set of all strings containing at most two zeros c.The set of all strings containing at least two zeros. d.The set of all strings containing the substring 00
***Programming language is Java. After looking at this scenario please look over the requirements at the...
***Programming language is Java. After looking at this scenario please look over the requirements at the bottom (in bold) THIS IS ALL THAT WAS PROVIDED. PLEASE SPECIFY ANY QUESTIONS IF THIS IS NOT CLEAR (don't just say more info, be specific)*** GMU in partnership with a local sports camp is offering a swimming camp for ages 10-18. GMU plans to make it a regular event, possibly once a quarter. You have been tasked to create an object-oriented solution to register,...
Please read the article and answear about questions. Determining the Value of the Business After you...
Please read the article and answear about questions. Determining the Value of the Business After you have completed a thorough and exacting investigation, you need to analyze all the infor- mation you have gathered. This is the time to consult with your business, financial, and legal advis- ers to arrive at an estimate of the value of the business. Outside advisers are impartial and are more likely to see the bad things about the business than are you. You should...
read Seasons of Love chapter:measuring a child's life after suicide. please answer the questions : reflect...
read Seasons of Love chapter:measuring a child's life after suicide. please answer the questions : reflect on what happens to the families when there is a suicide in the family, based on the Seasons of Love chapter...how should people be told? What details are best left unshared? below is the story These theories may have a certain face-validity, but they often neglect environmental or contextual factors that are innate to answering the question of “why” a person might engage in...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT