Recent questions tagged context-free-grammar

Show how, having filled in the table as in Question $4.4.9$, we can in $O(n)$ time recover a parse tree for $a_{1}a_{2}\cdot\cdot\cdot a_{n}$. Hint: modify the table so i...

Every language that has a context-free grammar can be recognized in at most $O(n^{3})$ time for strings of length $n$. A simple way to do so,called the Cocke- Younger-Ka...

Design grammars for the following languages:The set of all strings of $0's$ and $1's$ such that every $0$ is immediately followed by at least one $1$.The set of all strin...

Repeat Question $4.2.1$ for each of the following grammars and strings: $S\rightarrow 0S1\mid 01$ with string $000111$.$S\rightarrow +SS\mid \ast SS\mid a$ with string $+...

Construct a context-free grammar for roman numerals.

Construct unambiguous context-free grammars for each of the following languages. In each case show that your grammar is correct. Arithmetic expressions in postfix notatio...

What language is generated by the following grammars? In each case justify your answer. $S\rightarrow 0S1 \mid 01$$S\rightarrow +SS \mid -SS \mid a$$S\rightarrow S(S)S \m...

Consider the context-free grammar$S\rightarrow SS+\mid SS^{\ast}\mid a$Show how the string $aa+a^{\ast}$ can be generated by this grammar.Construct a parse tree for this ...

Let $L$ be the set of (codes for) context-free grammars $G$ such that $L(G)$ contains at least one palindrome. Show that $L$ is undecidable. Hint: Reduce PCP to $L$ by co...

Give LL grammars for the following languages, assuming $Σ =$ {$a,b, c$}.(i) $L=$ {$a^nb^mc^{n+m}:n\geq0,m\geq0$} .(ii) $L=$ {$a^{n+2}b^mc^{n+m}:n\geq0,m\geq0$} .(iii) $L=...

Show that if G is an LL (k) grammar, then L (G) is a deterministic context-free language.

Show that any LL grammar is unambiguous.

Find an LL grammar for the language L = {$w : n_a (w) = n_b (w)$}.

Show that the grammar $S_0\rightarrow aSbS,S\rightarrow aSbS|\lambda$ is an LL grammar and that it is equivalent to the grammar $S\rightarrow SS|aSb|ab$.

Let $CFG$ $G$ be the following grammar$.$ $S\rightarrow aSb \mid bY \mid Y a$$Y\rightarrow bY \mid aY \mid \epsilon$Give a simple description of $L(G)$ in English$.$ Us...

Give a counterexample to show that the following construction fails to prove that the class of context-free languages is closed under star. Let $A$ be a $\text{CFL}$ that...