Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged peter-linz
0
votes
0
answers
1
An Introduction to Formal Languages and Automata,Peter Linz,6th edition,exercise 3.3 q3
Find a regular grammar that generates the language L (aa ∗ (ab + a) ∗ ).
Find a regular grammar that generates the language L (aa ∗ (ab + a) ∗ ).
Silver_Reaper
518
views
Silver_Reaper
asked
Feb 6, 2023
Theory of Computation
theory-of-computation
regular-language
grammar
peter-linz
+
–
0
votes
1
answer
2
An Introduction to Formal Languages and Automata,6th edition,Exercise 2.3 Q2.
Convert the nfa in Exercise 13, Section 2.2, into an equivalent dfa.
Convert the nfa in Exercise 13, Section 2.2, into an equivalent dfa.
Silver_Reaper
691
views
Silver_Reaper
asked
Jan 28, 2023
Theory of Computation
theory-of-computation
peter-linz
finite-automata
+
–
0
votes
0
answers
3
An Introduction to Formal Languages and Automata Peter Linz 6th Edition.Exercise 2.1 4 d,e
For Σ = {a, b}, construct dfa’s that accept the sets consisting of: (d) all strings with at least one b and exactly two a’s. (e) all the strings with exactly two a’s and more than three b’s.
For Σ = {a, b}, construct dfa’s that accept the sets consisting of:(d) all strings with at least one b and exactly two a’s.(e) all the strings with exactly two a’s...
Silver_Reaper
394
views
Silver_Reaper
asked
Jan 24, 2023
Theory of Computation
theory-of-computation
peter-linz
finite-automata
+
–
2
votes
1
answer
4
Peter Linz Exercise 3.2 Question 2
Find a NFA that accepts the complement of the language (ab*aa + bba*ab)
Find a NFA that accepts the complement of the language (ab*aa + bba*ab)
ankit-saha
1.2k
views
ankit-saha
asked
Mar 26, 2022
Theory of Computation
peter-linz
theory-of-computation
regular-expression
+
–
0
votes
0
answers
5
Peter Linz Edition 5 Exercise 2.2 Question 7 (Page No. 79)
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 \}$
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 \}$
ankit-saha
396
views
ankit-saha
asked
Mar 19, 2022
Theory of Computation
peter-linz
theory-of-computation
peter-linz-edition5
finite-automata
+
–
1
votes
0
answers
6
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=$ {...
Naveen Kumar 3
718
views
Naveen Kumar 3
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
7
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?
Naveen Kumar 3
598
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
context-free-language
+
–
1
votes
2
answers
8
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.
Naveen Kumar 3
498
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
context-free-language
+
–
0
votes
0
answers
9
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...
Naveen Kumar 3
386
views
Naveen Kumar 3
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
10
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.
Naveen Kumar 3
280
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
11
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.
Naveen Kumar 3
223
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
inherently-ambiguous
+
–
0
votes
0
answers
12
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.
Naveen Kumar 3
258
views
Naveen Kumar 3
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
13
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.
Naveen Kumar 3
202
views
Naveen Kumar 3
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
14
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*).
Naveen Kumar 3
277
views
Naveen Kumar 3
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
15
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)$}.
Naveen Kumar 3
175
views
Naveen Kumar 3
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
16
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.
Naveen Kumar 3
270
views
Naveen Kumar 3
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
17
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$.
Naveen Kumar 3
207
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
18
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.
Naveen Kumar 3
457
views
Naveen Kumar 3
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
0
votes
0
answers
19
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.
Naveen Kumar 3
223
views
Naveen Kumar 3
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
0
votes
1
answer
20
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.
Naveen Kumar 3
343
views
Naveen Kumar 3
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
0
votes
1
answer
21
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.
Naveen Kumar 3
235
views
Naveen Kumar 3
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
0
votes
0
answers
22
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.
Naveen Kumar 3
164
views
Naveen Kumar 3
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
0
votes
1
answer
23
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...
Naveen Kumar 3
337
views
Naveen Kumar 3
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
0
votes
1
answer
24
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?
Naveen Kumar 3
294
views
Naveen Kumar 3
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
0
votes
0
answers
25
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?
Naveen Kumar 3
236
views
Naveen Kumar 3
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
0
votes
0
answers
26
Peter Linz Edition 4 Exercise 7.3 Question 7 (Page No. 200)
Give reasons why one might conjecture that the following language is not deterministic. $L =$ { $a^nb^mc^k : n = m$ or $m = k$}.
Give reasons why one might conjecture that the following language is not deterministic. $L =$ { $a^nb^mc^k : n = m$ or $m = k...
Naveen Kumar 3
583
views
Naveen Kumar 3
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
1
votes
1
answer
27
Peter Linz Edition 4 Exercise 7.3 Question 6 (Page No. 200)
For the language $L =$ {$a^nb^{2n} : n ≥ 0$}, show that $L^*$ is a deterministic context-free language.
For the language $L =$ {$a^nb^{2n} : n ≥ 0$}, show that $L^*$ is a deterministic context-free language.
Naveen Kumar 3
305
views
Naveen Kumar 3
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
0
votes
1
answer
28
Peter Linz Edition 4 Exercise 7.3 Question 4 (Page No. 200)
Is the language $L =$ {$a^nb^n : n ≥ 1$} $∪$ {$a$} deterministic?
Is the language $L =$ {$a^nb^n : n ≥ 1$} $∪$ {$a$} deterministic?
Naveen Kumar 3
299
views
Naveen Kumar 3
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
1
votes
1
answer
29
Peter Linz Edition 4 Exercise 7.3 Question 3 (Page No. 200)
Is the language $L =$ {$a^nb^n : n ≥ 1$} $∪$ {$b$} deterministic?
Is the language $L =$ {$a^nb^n : n ≥ 1$} $∪$ {$b$} deterministic?
Naveen Kumar 3
296
views
Naveen Kumar 3
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
0
votes
0
answers
30
Peter Linz Edition 4 Exercise 7.3 Question 2 (Page No. 200)
Show that $L =$ {$a^nb^m : m ≥ n + 2$} is deterministic.
Show that $L =$ {$a^nb^m : m ≥ n + 2$} is deterministic.
Naveen Kumar 3
180
views
Naveen Kumar 3
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
...
20
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register