The pumping lemma for CFLs:
Remember that the pumping lemma for the regular languages, a mathematically accurate statement of the intuitive notion ‘a FSM can count at most up to certain constant n’. It states that for any of regular language L, any adequately long word w in L can be split to three parts, w = x y z, in such a way that all strings x yk z, for any k ≥ 0, are as well in L.
PDAs that correspond to CFGs, can count randomly high - although essentially in the unary notation, that is, by storing k symbols to symbolize the number k. However the LIFO access limitation implies which the stack can only be employed to symbolize one single independent counter at a time. To understand what ‘independent’ signifies, consider a PDA which identifies a language of balanced parenthesis expressions, like ((([[..]]))). This task evidently calls for a random number of counters to be stored at similar time, each one dedicated to the counting his own sub-expression. In the illustration above, the counter for ‘(((‘should be saved whenever the counter for ‘[[‘is activated. Luckily, balanced parentheses are nested in such a manner that modifying from one counter to the other matches the LIFO access pattern of the stack - if a counter, run down to 0, is no longer required, the next counter on the top of stack is precisely the next one to be activated. Therefore, the many counters coded to the stack interact in a controlled way, they are not independent.
Pumping lemma for the CFLs is an accurate statement of this limitation. This asserts that each and every long word in L serves as a seed which produces an infinity of associated words which are also in L.
Theorem: For all CFL L there is a constant n in such a way that all z ∈ L of length |z| ≥ n can be written as: z = u v w x y such that the given holds:
i) v x ≠ ε , ii) |v w x| ≤ n, and iii) u vk w xk y ∈ L for all k ≥ 0.
Proof: Given that CFL L, select any G = G(L) in Chomsky NF. This implies that parse tree of any z ∈ L is a binary tree, as illustrated in the figure below. The length n of string at leaves and the height h of a binary tree are associated by h ≥ log n, that is, a long string needs a tall parse tree. By selecting the critical length n = 2 |V | + 1 we force the height of parse trees considered to be h ≥ |V| + 1. On a root-to-leaf path of length ≥ |V| + 1 we encounter at least |V| + 1 nodes labeled by the non-terminals. As G consists of only |V| distinct non-terminals, this implies that on certain long root-to-leaf path we should encounter 2 nodes labeled with the similar non-terminal, state W, as shown.
For such two occurrences of W (in specific, the two lowest ones), and for certain u, v, y, x, w ∈ A*, we encompass: S ->* u W y, W ->* v W x and W ->* w. However then we as well encompass W ->* v2 W x2, and in common, W ->* vk W xk, and S ->* u vk W xk y and S ->* u vk w xk y for all k ≥ 0, QED.
For problems where the intuition tells us ‘a PDA can’t do that’, the pumping lemma is frequently the perfect tool required to prove rigorously that a language is not CF. For illustration, intuition recommends that neither of the languages L1 = { 0k 1k 2k / k ≥ 0} or L2 = { w w / w ∈ {0, 1} } is recognizable by certain PDA.
For L1, the PDA would encompass to count up the 0s, and then count down the 1s to ensure that there are uniformly many 0s and 1s. Afterward, the counters is zero, and though we can count the 2s, cannot compare that number to the number of 0s, or of 1s, an information which is now lost.
For L2, the PDA would have to store the first half of input, namely w, and compare that to second half to confirm that the latter is as well w. While this worked trivially for palindromes, w wreversed, the order w w is the worst case probable for LIFO access: though the stack comprises all the information required, we cannot extract the info we require at the time we require it. The pumping lemma confirms such intuitive judgments.
Illustration: L1 = {0k 1k 2k / k ≥ 0} is not context free. Pf (by contradiction): Suppose L is CF, let n be the constant asserted by pumping lemma.
Consider z = 0n 1n 2n = u v w x y. Though we do not know where vwx is positioned in z, the assertion |v w x| ≤ n implies that v w x includes at most two different letters among 0, 1, 2. In another words, one or two of the three letters 0, 1, 2 is missing in the vwx. Now consider u v2 w x2 y. By pumping lemma, it should be in L. The assertion |v x| ≥ 1 implies that u v2 w x2 y is longer than u v w x y. However u v w x y had an equivalent number of 0s, 1s, and 2s, while u v2 w x2 y can’t, as only one or two of three distinct symbols rose in number. This contradiction proves the theorem.
Latest technology based Theory of Computation Online Tutoring Assistance
Tutors, at the www.tutorsglobe.com, take pledge to provide full satisfaction and assurance in Theory of Computation help via online tutoring. Students are getting 100% satisfaction by online tutors across the globe. Here you can get homework help for Theory of Computation, project ideas and tutorials. We provide email based Theory of Computation help. You can join us to ask queries 24x7 with live, experienced and qualified online tutors specialized in Theory of Computation. Through Online Tutoring, you would be able to complete your homework or assignments at your home. Tutors at the TutorsGlobe are committed to provide the best quality online tutoring assistance for Theory of Computation Homework help and assignment help services. They use their experience, as they have solved thousands of the Theory of Computation assignments, which may help you to solve your complex issues of Theory of Computation. TutorsGlobe assure for the best quality compliance to your homework. Compromise with quality is not in our dictionary. If we feel that we are not able to provide the homework help as per the deadline or given instruction by the student, we refund the money of the student without any delay.
TRF radio receiver is a straight radio receiver. It is termed as tuned radio frequency receiver.
tutorsglobe.com length of stamens assignment help-homework help by online sterile stamen tutors
explain Direct Expenses - Characteristics of Direct Expenses, After materials and labour the third element of cost is direct or chargeable expenses. These are expenses that can be suitably allocated directly to a cost unit.
Amino acids, Peptides and Proteins tutorial all along with the key concepts of Naming Amino acids, a-Amino acids, Configuration of Amino acids, synthesis of a-amino acids, Physical-chemical properties of amino acids, Polypeptides, Classification of Proteins and Properties of proteins
tutorsglobe.com oxygen family assignment help-homework help by online p block elements tutors
tutorsglobe.com enzymes assignment help-homework help by online energy and enzymes tutors
tutorsglobe.com chloroplast assignment help-homework help by online cell organelles tutors
rectify the fault in fm receiver - noisy reception - first of all switch on the receiver, hearing the programme with noisy sound.
The main idea behind hair dryers is pretty much simple, but generating one for mass consumption needs some hard thinking regarding to the safety features.
www.tutorsglobe.com offers reversible addition reactions homework help, reversible addition reactions assignment help, online tutoring assistance, organic chemistry solutions by online qualified tutor's help.
Radiochemical Method tutorial all along with the key concepts of History and Application, Interaction of radiation with matter, Radiation Detection, Radioanalytical Chemistry Principles, Gas Ionization Detectors and Solid-State Detectors
Other Types of Bonding tutorial all along with the key concepts of Metallic bonding, Explaining the Physical Properties of Metals, Hydrogen bonding, Hydrogen Bonds in Biology, Other intermolecular forces, London dispersion forces, Dipole-dipole interactions
tutorsglobe.com mechanism of fission assignment help-homework help by online type of nuclear reaction tutors
The cathode of the picture tube is delivered 80V (p-p) video signal. The tungsten filament is provided 6.3 V AC. Therefore cathode is not directly heated and produces a lot of electrons.
tutorsglobe.com light microscopy assignment help-homework help by online light and electron microscope tutors
1934639
Questions Asked
3689
Tutors
1481103
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!