Recent questions tagged peter-linz

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

Show that $L = \{a^nb^m,n< 2m \}$ is a deterministic context-free language.

Design an nfa with no more than five states for the set $\left \{ abab^n: n >0 \right \} \cup \left \{ ab{a}^n : n\geq 0 \right \}$

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