# Recent questions tagged peter-linz 1 vote
1
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^jb^n : n ≥ 0, j ≥ 0$}. (d) $L=$ {$a^nb^ja^kb^l : n + j ≤ k + l$}. (e)$L=$ {$a^nb^ja^kb^l : n ≤ k, j ≤ l$}. (f) $L=$ {$a^nb^nc^j : n ≤j$}. (g) $L=$ {$w ∈$ {$a, b, c$}* $: n_a(w)= n_b (w)=2n_c(w)$}.
2
Is the language L = {$a^nb^m : n = 2^m$} context-free?
3
Show that the language $L=${$a^nb^nc^m,n\neq m$} is not context-free.
4
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=$ {$a^nb^{n+2}c^{m}:n\geq0,m\gt1$} . (iv) $L=$ {$w:n_a(w)\lt n_b(w)$} . (v) $L=$ {$w:n_a(w)+n_b(w)\neq n_c(w)$} .
5
Let G be a context-free grammar in Greibach normal form. Describe an algorithm which, for any given k, determines whether or not G is an LL (k) grammar.
6
Show that a deterministic context-free language is never inherently ambiguous.
7
Show that if G is an LL (k) grammar, then L (G) is a deterministic context-free language.
8
Show that any LL grammar is unambiguous.
9
Construct an LL grammar for the language L (a*ba) ∪ L (abbb*).
10
Find an LL grammar for the language L = {$w : n_a (w) = n_b (w)$}.
11
Show that the grammar for L = {$w : n_a (w) = n_b (w)$} which is, $S\rightarrow SS,S\rightarrow \lambda,S\rightarrow aSb,S\rightarrow bSa$ is not an LL grammar.
12
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$.
13
Give an example of a deterministic context-free language whose reverse is not deterministic.
14
Show that under the conditions of Exercise 16, $L_1 ∩ L_2$ is a deterministic context-free language.
15
Show that if $L_1$ is deterministic context-free and $L_2$ is regular, then the language $L_1 ∪ L_2$ is deterministic context-free.
16
Show that every regular language is a deterministic context-free language.
17
Show that $L =$ {$w ∈$ {$a, b$}$^* : n_a (w) ≠ n_b (w)$} is a deterministic context-free language.
18
While the language in Exercise 9 is deterministic, the closely related language $L =$ {$ww^R : w ∈${$a,b$}$^*$} is known to be nondeterministic. Give arguments that make this statement plausible.
19
Is the language {$wcw^R : w ∈${$a, b$}$^*$} deterministic?
20
Is the language $L =$ {$a^nb^m : n = m$ or $n = m + 2$} deterministic?
21
Give reasons why one might conjecture that the following language is not deterministic. $L =$ { $a^nb^mc^k : n = m$ or $m = k$}.
1 vote
22
For the language $L =$ {$a^nb^{2n} : n ≥ 0$}, show that $L^*$ is a deterministic context-free language.
23
Is the language $L =$ {$a^nb^n : n ≥ 1$} $∪$ {$a$} deterministic?
1 vote
24
Is the language $L =$ {$a^nb^n : n ≥ 1$} $∪$ {$b$} deterministic?
25
Show that $L =$ {$a^nb^m : m ≥ n + 2$} is deterministic.
26
Show that $L =$ {$a^nb^{2n} : n ≥ 0$} is a deterministic context-free language.
27
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 M such that L = L (M).
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 $δ(q_0, a,z) =$ {$(q_0, Az)$}, $δ (q_0,b, A) =$ {$(q_0, AA)$}, $δ(q_0, a, A) =$ {$(q_1,λ)$}.
find an npda for the language $L =${ $ww^R : w ∈$ {a, b}$^+$}