Give a grammar for 0n 12n 23n n 0 Im stuyding about Turing
Give a grammar for {0n 12n 23n : n 0}
I\'m stuyding about Turing machine and un/decidable languages. The given question is not part of those chapters.
I do not know what kind of grammar I have to answer for this question. Please help me.
Solution
Answer: --->>>>>>
A= {0n 12n 23n : n 0}
Assume that A is a ContextFreeLanguage. Let p be the pumping length of the pumping lemma for ContextFreeLanguages, and consider string s = 0^p*1^2p*2^3p belongs to A. Note that |s| = 6p > p,
so the pumping lemma will hold. Thus, there exist strings u, v, x, y, z such that s =uvxyz = 0^p*1^2p*2^3p, uvixyiz belongs to A for all i 0, and |vy| 1.
We now consider all of the possible choices for v and y:
Suppose strings v and y are uniform (e.g., v = 0j for some j 0, and y = 1k for some k 0). Then |vy| 1 implies that j 1 or k 1 (or both), so uv2xy3z
won’t have the correct number of 0’s at the beginning, 1’s in the middle, and 2’s at the end. Hence, uv2xy2z Not Belongs to A.
Now suppose strings v and y are not both uniform. Then uv2xy3z will not have
the form 0 · · · 01 · · · 10 · · · 0. Hence, uv2xy3z Not Belongs to A.
Thus, there are no options for v and y such that uvixyiz Belongs to A for all i 0. This is a contradiction, so A is not a ContextFreeLanguage.
