New answers tagged

0

Proposition 6.11 Full manuscript: https://www.cis.upenn.edu/~jean/gbooks/tocnotes.html Definition 3.11.2: Given a context-free grammar $G = (V, \Sigma, P, > S)$, for any $A \in N$, if $\pi: A \stackrel{n}{\implies} \alpha$ is a derivation in $G$, we construct an A-derivation tree $t_\pi$ with yield $\alpha$ as follows. if $n = 0$, then $t_\pi$ is the ...


1

In a word, no. Every tree has exactly one left-to-right depth-first traverse and exactly one right-to-left depth-first traverse, either of which can be used to unambiguously recreate the original tree. Since the leftmost derivation of a sentence is just another way of writing the left-to-right depth-first traverse of the parse tree for that sentence (and ...


0

The language is context free. Here is a hint: as you have proved, it isn't regular. Therefore, when you try to construct a PDA for this language you will have to use the stack. Try to think how to count numbers using the stack, maybe start with a simpler language like $\{0^n1^m\mid n\ge m\}$. This is the main "crux" of your problem :)


1

In fact, you have identified a tip! Let me make it more explicit. Suppose $L$ is context-free and $p>0$ is a pumping length for it as in the pumping lemma for context-free language. Try pumping up or down the word $a^pb^{p+1}c^p$ out of $L$. (You can also pump up or down the word $a^pb^pc^{p+1}$ out of $L$.)


Top 50 recent answers are included