--%>
Assignment Help - homework help

  The Pumping Lemma for CFLs, Context Free Grammars & Languages

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.

1216_pumping lemma.jpg

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.