Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Filter
Profile
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
Questions by Naveen Kumar 3
1
votes
0
answers
1
Peter Linz Edition 4 Exercise 8.1 Question 8 (Page No. 212)
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$ ... $ L=$ {$a^nb^nc^j : n ≤j$}. (g) $L=$ {$w ∈$ {$a, b, c$}* $: n_a(w)= n_b (w)=2n_c(w)$}.
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=$ {...
732
views
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
pumping-lemma
proof
+
–
2
votes
2
answers
2
Peter Linz Edition 4 Exercise 8.1 Question 5 (Page No. 212)
Is the language L = {$a^nb^m : n = 2^m$} context-free?
Is the language L = {$a^nb^m : n = 2^m$} context-free?
620
views
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
context-free-language
+
–
1
votes
2
answers
3
Peter Linz Edition 4 Exercise 8.1 Question 1 (Page No. 212)
Show that the language $L=${$a^nb^nc^m,n\neq m$} is not context-free.
Show that the language $L=${$a^nb^nc^m,n\neq m$} is not context-free.
503
views
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
context-free-language
+
–
0
votes
0
answers
4
Peter Linz Edition 4 Exercise 7.4 Question 9 (Page No. 204)
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)$} .
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...
392
views
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
context-free-grammar
+
–
1
votes
1
answer
5
Peter Linz Edition 4 Exercise 7.4 Question 8 (Page No. 204)
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.
Let G be a context-free grammar in Greibach normal form. Describe an algorithm which, for anygiven k, determines whether or not G is an LL (k) grammar.
294
views
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
6
Peter Linz Edition 4 Exercise 7.4 Question 7 (Page No. 204)
Show that a deterministic context-free language is never inherently ambiguous.
Show that a deterministic context-free language is never inherently ambiguous.
227
views
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
inherently-ambiguous
+
–
0
votes
0
answers
7
Peter Linz Edition 4 Exercise 7.4 Question 6 (Page No. 204)
Show that if G is an LL (k) grammar, then L (G) is a deterministic context-free language.
Show that if G is an LL (k) grammar, then L (G) is a deterministic context-free language.
267
views
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
0
answers
8
Peter Linz Edition 4 Exercise 7.4 Question 5 (Page No. 204)
Show that any LL grammar is unambiguous.
Show that any LL grammar is unambiguous.
209
views
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
1
answer
9
Peter Linz Edition 4 Exercise 7.4 Question 4 (Page No. 204)
Construct an LL grammar for the language L (a*ba) ∪ L (abbb*).
Construct an LL grammar for the language L (a*ba) ∪ L (abbb*).
282
views
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
0
answers
10
Peter Linz Edition 4 Exercise 7.4 Question 3 (Page No. 204)
Find an LL grammar for the language L = {$w : n_a (w) = n_b (w)$}.
Find an LL grammar for the language L = {$w : n_a (w) = n_b (w)$}.
178
views
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
1
answer
11
Peter Linz Edition 4 Exercise 7.4 Question 2 (Page No. 204)
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.
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.
277
views
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
context-free-grammar
+
–
0
votes
0
answers
12
Peter Linz Edition 4 Exercise 7.4 Question 1 (Page No. 204)
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$.
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$.
214
views
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
13
Peter Linz Edition 4 Exercise 7.3 Question 18 (Page No. 200)
Give an example of a deterministic context-free language whose reverse is not deterministic.
Give an example of a deterministic context-free language whose reverse is not deterministic.
471
views
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
0
votes
0
answers
14
Peter Linz Edition 4 Exercise 7.3 Question 17 (Page No. 200)
Show that under the conditions of Exercise 16, $L_1 ∩ L_2$ is a deterministic context-free language.
Show that under the conditions of Exercise 16, $L_1 ∩ L_2$ is a deterministic context-free language.
226
views
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
0
votes
1
answer
15
Peter Linz Edition 4 Exercise 7.3 Question 16 (Page No. 200)
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.
Show that if $L_1$ is deterministic context-free and $L_2$ is regular, then the language $L_1 ∪ L_2$ isdeterministic context-free.
357
views
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
0
votes
1
answer
16
Peter Linz Edition 4 Exercise 7.3 Question 15 (Page No. 200)
Show that every regular language is a deterministic context-free language.
Show that every regular language is a deterministic context-free language.
240
views
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
0
votes
0
answers
17
Peter Linz Edition 4 Exercise 7.3 Question 11 (Page No. 200)
Show that $L =$ {$w ∈$ {$a, b$}$^* : n_a (w) ≠ n_b (w)$} is a deterministic context-free language.
Show that $L =$ {$w ∈$ {$a, b$}$^* : n_a (w) ≠ n_b (w)$} is a deterministic context-free language.
166
views
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
0
votes
1
answer
18
Peter Linz Edition 4 Exercise 7.3 Question 10 (Page No. 200)
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.
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 mak...
342
views
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
0
votes
1
answer
19
Peter Linz Edition 4 Exercise 7.3 Question 9 (Page No. 200)
Is the language {$wcw^R : w ∈ ${$a, b$}$^*$} deterministic?
Is the language {$wcw^R : w ∈ ${$a, b$}$^*$} deterministic?
299
views
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
0
votes
0
answers
20
Peter Linz Edition 4 Exercise 7.3 Question 8 (Page No. 200)
Is the language $L =$ {$a^nb^m : n = m$ or $n = m + 2$} deterministic?
Is the language $L =$ {$a^nb^m : n = m$ or $n = m + 2$} deterministic?
244
views
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
Page:
1
2
3
4
5
6
...
19
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register