Recent questions tagged peter-linz-edition4

A run in a string is a substring of length at least two, as long as possible and consisting entirely of the same symbol. For instance, the string abbbaab contains a run o...

Determine whether or not the following languages are context-free.(a) $L=$ {$a^nww^Ra^n : n ≥ 0, w ∈$ {$a,b$}*}(b) $L=$ {$a^nb^ja^nb^j : n ≥ 0, j ≥ 0$}.(C) $L=$ {$a^nb^ja...

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 a deterministic context-free language is never inherently ambiguous.

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$.

Give an example of a deterministic context-free language whose reverse is not deterministic.

Show that under the conditions of Exercise 16, $L_1 ∩ L_2$ is a deterministic context-free language.

Is the language $L =$ {$a^nb^m : n = m$ or $n = m + 2$} deterministic?

Give reasons why one might conjecture that the following language is not deterministic. $L =$ { $a^nb^mc^k : n = m$ or $m = k...

Show that $L =$ {$a^nb^m : m ≥ n + 2$} is deterministic.

Show that $L =$ {$a^nb^{2n} : n ≥ 0$} is a deterministic context-free language.

Give a construction by which an arbitrary context-free grammar can be used in the proof of Theorem 7.1.Theorem 7.1: For any context-free language L, there exists an npda ...

Give full details of the proof of Theorem 7.2 .Theorem 7.2 : If L = L (M) for some npda M, then L is a context-free language.

Find a context-free grammar that generates the language accepted by the npda $M =$ ({$q_0,q_1$}, {$a,b$}, {$A, z$}$,δ, q_0, z,$ {$q_1$}), with transitions ...