Question

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. {aⁿ b^m | 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

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