bet you thought you were done with the pumpinglemma.3a. [10 points] SupposeLis a
ID: 3739461 • Letter: B
Question
bet you thought you were done with the pumpinglemma.3a. [10 points] SupposeLis a regular language, and letpbe its pumping length. Prove thatLis infinite iffLcontains a string whose length is?pand<2p.3b. [10 points] We saw in class thatADFAandEDFAare decidable. Now show thatFDFA=hMi:Mis a DFA andL(M) is finiteis decidable, by using part 3a. (By the way,the same approach works to show thatFPDAis decidable, using the pumping lemma forcontext-free languages, which we unfortunately didn’t have time to cover this semester.)
Will thumbs up for both ansswers. Please show all steps!
3. [20 points I bet you thought you were done with the pumping lemma 3a. [10 points] Suppose L is a regular language, and let p be its pumping length. Prove that L is infinite iff L contains a string whose length is-p and 2p. 3b. [10 points We saw in class that ADFA and EDFA are decidable. Now show that FDFA M) : M is a DFA and L(M) is finite} is decidable, by using part 3a. (By the way, the same approach works to show that FpDa is decidable, using the pumping lemma for context-free languages, which we unfortunately didn't have time to cover this semester.)Explanation / Answer
Pumping Lemma
There are two Pumping Lemmas, which are characterized for
1. Regular Languages, and
2. Context – Free Languages
Drawing Lemma for Regular Languages
For any customary dialect L, there exists a whole number n, to such an extent that for all x ? L with |x| ? n, there exists u, v, w ? ??, to such an extent that x = uvw, and
(1) |uv| ? n
(2) |v| ? 1
(3) for all I ? 0: uviw ? L
In straightforward terms, this implies if a string v is 'pumped', i.e., if v is embedded any number of times, the resultant string still stays in L.
Pumping Lemma is utilized as a proof for anomaly of a dialect. In this way, if a dialect is normal, it generally fulfills pumping lemma. In the event that there exists no less than one string produced using pumping which isn't in L, at that point L is without a doubt not customary.
The inverse of this may not generally be valid. That is, if Pumping Lemma holds, it doesn't imply that the dialect is consistent.
p1
For instance, let us demonstrate L01 = {0n1n | n ? 0} is unpredictable.
Give us a chance to expect that L is customary, at that point by Pumping Lemma the above given guidelines take after.
Presently, let x ? L and |x| ? n. In this way, by Pumping Lemma, there exists u, v, w with the end goal that (1) – (3) hold.
We demonstrate that for all u, v, w, (1) – (3) does not hold.
On the off chance that (1) and (2) hold then x = 0n1n = uvw with |uv| ? n and |v| ? 1.
In this way, u = 0a, v = 0b, w = 0c1n where : a + b ? n, b ? 1, c ? 0, a + b + c = n
In any case, at that point (3) falls flat for I = 0
uv0w = uw = 0a0c1n = 0a + c1n ? L, since a + c ? n.
p2
Directing Lemma for without context Languages (CFL)
Drawing Lemma for CFL states that for any Context Free Language L, it is conceivable to discover two substrings that can be 'pumped' any number of times and still be in a similar dialect. For any dialect L, we break its strings into five sections and pump second and fourth substring.
Drawing Lemma, here likewise, is utilized as an apparatus to demonstrate that a dialect isn't CFL. Since, if any one string does not fulfill its conditions, at that point the dialect isn't CFL.
In this way, if L is a CFL, there exists a whole number n, to such an extent that for all x ? L with |x| ? n, there exists u, v, w, x, y ? ??, to such an extent that x = uvwxy, and
(1) |vwx| ? n
(2) |vx| ? 1
(3) for all I ? 0: uviwxiy ? L
p3
For above case, 0n1n is CFL, as any string can be the aftereffect of pumping at two spots, one for 0 and other for 1.
Give us a chance to demonstrate, L012 = {0n1n2n | n ? 0} isn't sans context.
Give us a chance to expect that L is without context, at that point by Pumping Lemma, the above given tenets take after.
Presently, let x ? L and |x| ? n. Along these lines, by Pumping Lemma, there exists u, v, w, x, y with the end goal that (1) – (3) hold.
We demonstrate that for all u, v, w, x, y (1) – (3) don't hold.
On the off chance that (1) and (2) hold then x = 0n1n2n = uvwxy with |vwx| ? n and |vx| ? 1.
(1) reveals to us that vwx does not contain both 0 and 2. In this way, either vwx has no 0's, or vwx has no 2's. Consequently, we have two cases to consider.
Assume vwx has no 0's. By (2), vx contains a 1 or a 2. In this way uwy has 'n' 0's and uwy either has not as much as 'n' 1's or has not as much as 'n' 2's.
In any case, (3) reveals to us that uwy = uv0wx0y ? L.
Thus, uwy has an equivalent number of 0's, 1's and 2's gives us a logical inconsistency. The situation where vwx has no 2's is comparable and furthermore gives us a logical inconsistency. Along these lines L isn't without setting.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.