D2L Bright space 1. Consider the language for 1\"2 f m LB (a Prove that LB is no

Question

D2L Bright space 1. Consider the language for 1"2 f m LB (a Prove that LB is not regular. You may use the pumping lemma and closure properties for regular languages. (b) Give a Context-Free Grammar for LB 2. Consider the following Context-Free Grammar: A alas I BAA Give parse trees and leftmost derivations for each of the following strings. (a) ababba (b) aaabbb (c) baaalbab 3. Design context-free grammars that generate each of the following languages (all over the alphabet (0,1) (a) w E (0,1) where w has odd length and its first, last, and middle symbols are the same (b) (0"1" n m +2)

Explanation / Answer

(a) If L is regular then let us consider only the case when m=1, the L1(subset of L) will be 01^n2^h is also regular. Then L2 1^n2^h should also be regular, as this is only removing the first 0 from all the strings.

Let p be the pumping length. Then S = 1^p2^p belongs to L. We should divide this in to S = xyz.

As |y|>=1 and |xy|<=p, the y = |1|^r where r>=0

So x(y^0)z = 1^(p-r)2^p, in this case p-r<p so this does not belong to L2. So L2 is not regular, so L1 which is 0L2 is also not regular.

(b)

S -> 0A | B
A -> 1A2 | 1A |
B -> 0B | C
C -> 1C | D
D -> 2D |

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.