Already have an account? Get multiple benefits of using own account!
Login in your account..!
Remember me
Don't have an account? Create your account in less than a minutes,
Forgot password? how can I recover my password now!
Enter right registered email to receive password!
Applying the pumping lemma is not fundamentally di?erent than applying (general) su?x substitution closure or the non-counting property. The pumping lemma is a little more complicated-rather than just the single universal quanti?er ("for all languages L") and single existential quanti?er ("there exists n"), we have a nest of alternating quanti?ers (denoting "for all" as ∀ and "there exists" as ∃):
(∀L)[L regular ⇒
(∃n)[
(∀x)[x ∈ L and |x| ≥ n ⇒
(∃u, v,w)[x = uvw and
|uv| ≤ n and
|v| ≥ 1 and
(∀i ≥ 0)[uviw ∈ L]]]]].
Just as with the lemmas for the local languages, we will approach this as an adversary game. Our proof will consist of a strategy for showing that L fails to satisfy the pumping lemma. Our choices are the "for all"s; the "there exists"s are our adversary's choices. There are just a few more rounds in this game than there were in the lemmas for the local languages. The key things are being clear about which are our choices and which are the adversary's and making sure that our strategy accounts for every legal choice the adversarymight make.
The game starts with our choice of the L we wish to prove to be non regular. Our adversary then chooses some n, we choose a string x ∈ L of length at least n, etc. We win if, at the end of this process, we can choose i such that uviw ∈ L. Of course, our strategy at each step will depend on the choices our adversary has made.
What we end up with is a proof by contradiction. For instance:
To show that Lab = {ajbj| j ≥ 0} is not regular.
automata of atm machine
write short notes on decidable and solvable problem
This close relationship between the SL2 languages and the recognizable languages lets us use some of what we know about SL 2 to discover properties of the recognizable languages.
Ask queyystion #Minimum 100 words accepted#
We will assume that the string has been augmented by marking the beginning and the end with the symbols ‘?' and ‘?' respectively and that these symbols do not occur in the input al
Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b.
What are the benefits of using work breakdown structure, Project Management
how many pendulum swings will it take to walk across the classroom?
how to find whether the language is cfl or not?
shell script to print table in given range
Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!
whatsapp: +91-977-207-8620
Phone: +91-977-207-8620
Email: [email protected]
All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd