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

- {a
^{n}b^{m}| m != n, n >= 0} - {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

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 = {www| w € {a, b}*}

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
(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 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 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 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

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 36 minutes ago

asked 56 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago

asked 2 hours ago

asked 3 hours ago

asked 3 hours ago

asked 3 hours ago

asked 3 hours ago

asked 4 hours ago

asked 4 hours ago