Recent questions tagged peter-linz-edition4 / GATE Overflow for GATE CSE

0 votes

0 answers

31

Peter Linz Edition 4 Exercise 7.2 Question 11,12,13 (Page No. 195)
Show that the npda in Example 7.8 accepts L (aa*b). Find the grammar that generates Example 7.8 and prove that this grammar generates the language L (aa*b). show that the variable ($q_0zq_1$) is useless. (see page no. 191-193) Example 7.8 : ... $\delta(q_0,b,A)=${$(q_1,\lambda)$}, $\delta(q_1,\lambda,z)=${$(q_2,\lambda)$}.

Show that the npda in Example 7.8 accepts L (aa*b).Find the grammar that generates Example 7.8 and prove that this grammar generates the language L (aa*b).show that the v...

Naveen Kumar 3

400 views

Naveen Kumar 3 asked Jun 23, 2019

1 votes

1 answer

32

Peter Linz Edition 4 Exercise 7.2 Question 10 (Page No. 195)
Find an npda with two states that accepts $L =$ {$a^nb^{2n} : n ≥1$}.

Find an npda with two states that accepts $L =$ {$a^nb^{2n} : n ≥1$}.

Naveen Kumar 3

487 views

Naveen Kumar 3 asked Jun 22, 2019

1 votes

2 answers

33

Peter Linz Edition 4 Exercise 7.2 Question 9 (Page No. 195)
Find an npda with two states for the language $L =$ {$a^nb^{n+1} : n ≥ 0$}.

Find an npda with two states for the language $L =$ {$a^nb^{n+1} : n ≥ 0$}.

Naveen Kumar 3

1.4k views

Naveen Kumar 3 asked Jun 22, 2019

0 votes

0 answers

34

Peter Linz Edition 4 Exercise 7.2 Question 7,8 (Page No. 195)
Show that “For every npda $M$, there exists an npda $\widehat M$ with at most three states, such that $L (M) = L (\widehat M )$. Show how the number of states of $\widehat M $ in the above exercise can be reduced to two.

Show that “For every npda $M$, there exists an npda $\widehat M$ with at most three states, such that $L (M) = L (\widehat M )$.Show how the number of states of $\wideh...

Naveen Kumar 3

213 views

Naveen Kumar 3 asked Jun 22, 2019

0 votes

0 answers

35

Peter Linz Edition 4 Exercise 7.2 Question 5 (Page No. 195)
Construct an npda corresponding to the grammar $S\rightarrow aABB|aAA,$ $A\rightarrow aBB|a,$ $B\rightarrow bBB|A.$

Construct an npda corresponding to the grammar $S\rightarrow aABB|aAA,$ $A\rightarrow aBB|a,$ $B\rightarrow bBB|A.$

Naveen Kumar 3

264 views

Naveen Kumar 3 asked Jun 22, 2019

0 votes

1 answer

36

Peter Linz Edition 4 Exercise 7.2 Question 4 (Page No. 195)
Construct an npda that accepts the language generated by the grammar $S → aSSS|ab$.

Construct an npda that accepts the language generated by the grammar $S → aSSS|ab$.

Naveen Kumar 3

306 views

Naveen Kumar 3 asked Jun 22, 2019

0 votes

0 answers

37

Peter Linz Edition 4 Exercise 7.2 Question 3 (Page No. 195)
Construct an npda that accepts the language generated by the grammar $S\rightarrow aSbb|aab$.

Construct an npda that accepts the language generated by the grammar $S\rightarrow aSbb|aab$.

Naveen Kumar 3

201 views

Naveen Kumar 3 asked Jun 22, 2019

0 votes

0 answers

38

Peter Linz Edition 4 Exercise 7.2 Question 2 (Page No. 195)
Prove that the pda in Example 7.6 accepts the language $L =$ {$a^{n+1}b^{2n} : n ≥ 0$ }.

Prove that the pda in Example 7.6 accepts the language $L =$ {$a^{n+1}b^{2n} : n ≥ 0$ }.

Naveen Kumar 3

189 views

Naveen Kumar 3 asked Jun 22, 2019

0 votes

0 answers

39

Peter Linz Edition 4 Exercise 7.2 Question 1 (Page No. 195)
Show that the pda constructed in Example 7.6 accepts the string $aaabbbb$ that is in the language generated by the given grammar. Example 7.6: Construct a pda that accepts the language generated by a grammar with productions $S\rightarrow aSbb|a.$

Show that the pda constructed in Example 7.6 accepts the string $aaabbbb$ that is in the languagegenerated by the given grammar.Example 7.6: Construct a pda that accepts...

Naveen Kumar 3

195 views

Naveen Kumar 3 asked Jun 22, 2019

0 votes

0 answers

40

Peter Linz Edition 4 Exercise 7.1 Question 16 (Page No. 184)
We can define a restricted npda as one that can increase the length of the stack by at most one symbol in each move, changing Definition 7.1 so that $\delta :$Q x $(\sum \cup$ {$\lambda$}$) $ ... the initial state of the control unit, $z ∈ Γ$ is the stack start symbol, $F ⊆ Q$ is the set of final states.

We can define a restricted npda as one that can increase the length of the stack by at most onesymbol in each move, changing Definition 7.1 so that $\...

Naveen Kumar 3

714 views

Naveen Kumar 3 asked Jun 22, 2019

0 votes

0 answers

41

Peter Linz Edition 4 Exercise 7.1 Question 14 (Page No. 184)
Find an npda with no more than two internal states that accepts the language $L (aa^*ba^*)$.

Find an npda with no more than two internal states that accepts the language $L (aa^*ba^*)$.

Naveen Kumar 3

250 views

Naveen Kumar 3 asked Jun 22, 2019

0 votes

0 answers

42

Peter Linz Edition 4 Exercise 7.1 Question 13 (Page No. 184)
What language is accepted by the npda in Exercise 11 if we use $F =$ {$q_0, q_1, q_2$}?

What language is accepted by the npda in Exercise 11 if we use $F =$ {$q_0, q_1, q_2$}?

Naveen Kumar 3

199 views

Naveen Kumar 3 asked Jun 22, 2019

0 votes

0 answers

43

Peter Linz Edition 4 Exercise 7.1 Question 11 (Page No. 184)
What language is accepted by the npda $M =$ ({$q_0, q_1, q_2$}, {$a, b$}, {$a, b, z$}, $δ, q_0, z$, {$q_2$}) with transitions $\delta(q_0,a,z)=${$(q_1,a),(q_2,\lambda)$}, $\delta(q_1,b,a)=${$(q_1,b)$}, $\delta(q_1,b,b)=${$(q_1,b)$}, $\delta(q_1,a,b)=${$(q_2,\lambda)$} ?

What language is accepted by the npda $M =$ ({$q_0, q_1, q_2$}, {$a, b$}, {$a, b, z$}, $δ, q_0, z$, {$q_2$}) withtransitions $\delta(q_0,a,z)=${$(q_...

Naveen Kumar 3

245 views

Naveen Kumar 3 asked Jun 22, 2019

0 votes

0 answers

44

Peter Linz Edition 4 Exercise 7.1 Question 10 (Page No. 184)
What language is accepted by the pda $M= (${$q_0,q_1,q_2,q_3,q_4,q_5$},{$a,b$},{$0,1,a$},$\delta,q_0,z,${$q_5$}), with $\delta(q_0,b,z)=${$(q_1,1z)$}, $\delta(q_0,b,1)=${$(q_1,11)$}, $\delta(q_2,a,1)=${$(q_3,\lambda)$}, $\delta(q_3,a,1)=${$(q_4,\lambda)$} $\delta(q_4,a,z)=${$(q_4,z),(q_5,z)$} ?

What language is accepted by the pda $M= (${$q_0,q_1,q_2,q_3,q_4,q_5$},{$a,b$},{$0,1,a$},$\delta,q_0,z,${$q_5$}),with $\delta(q_0,b,z)=...

Naveen Kumar 3

215 views

Naveen Kumar 3 asked Jun 22, 2019

0 votes

1 answer

45

Peter Linz Edition 4 Exercise 7.1 Question 9 (Page No. 183)
Is it possible to find a dfa that accepts the same language as the pda $M= (${$q_0,q_1$},{$a,b$},{$z$},$\delta,q_0,z,${$q_1$}), with $\delta(q_0,a,z)=${$(q_1,z)$}, $\delta(q_0,b,z)=${$(q_0,z)$}, $\delta(q_1,a,z)=${$(q_1,z)$}, $\delta(q_1,b,z)=${$(q_0,z)$} ?

Is it possible to find a dfa that accepts the same language as the pda $M= (${$q_0,q_1$},{$a,b$},{$z$},$\delta,q_0,z,${$q_1$}),with ...

Naveen Kumar 3

526 views

Naveen Kumar 3 asked Apr 20, 2019

0 votes

0 answers

46

Peter Linz Edition 4 Exercise 7.1 Question 8 (Page No. 183)
Find an npda for the language $L =$ {$ab (ab)^n b (ba)^n : n ≥ 0$}.

Find an npda for the language $L =$ {$ab (ab)^n b (ba)^n : n ≥ 0$}.

Naveen Kumar 3

343 views

Naveen Kumar 3 asked Apr 20, 2019

0 votes

0 answers

47

Peter Linz Edition 4 Exercise 7.1 Question 7 (Page No. 183)
Find an npda for the concatenation of $L (a^*)$ and the language in Exercise 6.

Find an npda for the concatenation of $L (a^*)$ and the language in Exercise 6.

Naveen Kumar 3

376 views

Naveen Kumar 3 asked Apr 20, 2019

0 votes

0 answers

48

Peter Linz Edition 4 Exercise 7.1 Question 6 (Page No. 183)
Find an npda on $Σ =$ {$a, b, c$} that accepts the language $L=${$w_1cw_2:w_1,w_2∈$ {$a,b$}$^*,w_1\neq w_2^R$}.

Find an npda on $Σ =$ {$a, b, c$} that accepts the language $L=${$w_1cw_2:w_1,w_2∈$ {$a,b$}$^*,w_1\neq w_2^R$}.

Naveen Kumar 3

411 views

Naveen Kumar 3 asked Apr 20, 2019

0 votes

0 answers

49

Peter Linz Edition 4 Exercise 7.1 Question 5 (Page No. 183)
Construct an npda that accepts the language $L =$ {$a^nb^m : n ≥ 0, n ≠ m$}.

Construct an npda that accepts the language $L =$ {$a^nb^m : n ≥ 0, n ≠ m$}.

Naveen Kumar 3

223 views

Naveen Kumar 3 asked Apr 20, 2019

0 votes

0 answers

50

Peter Linz Edition 4 Exercise 7.1 Question 4 (Page No. 183)
Construct npda's that accept the following languages on $Σ =$ {$a, b, c$}. (a) $L =$ {$a^nb^{2n} : n ≥ 0$}. (b) $L =$ {$wcw^R : w ∈$ {$a, b$}$^*$}. (c) $L =$ {$a^nb^mc^{n+m} : n ≥ 0, m ≥ 0$}. (d) $L =$ ... . (h) here (i) $L =$ {$w : n_a (w) + n_b (w) = n_c (w)$}. (j) here. (k) $L =$ {$w : n_a (w) < n_b (w)$}.

Construct npda's that accept the following languages on $Σ =$ {$a, b, c$}.(a) $L =$ {$a^nb^{2n} : n ≥ 0$}.(b) $L =$ {$wcw^R : w ∈$ {$a, b$}$^*$}.(c) $L =$ {$a^nb^mc^...

Naveen Kumar 3

346 views

Naveen Kumar 3 asked Apr 20, 2019

1 votes

0 answers

51

Peter Linz Edition 4 Exercise 7.1 Question 3 (Page No. 183)
Construct npda's that accept the following regular languages. (a) $L_1 = L (aaa^*b)$. (b) $L_1 = L (aab^*aba^*)$. (c & d here)

Construct npda's that accept the following regular languages.(a) $L_1 = L (aaa^*b)$.(b) $L_1 = L (aab^*aba^*)$.(c & d here)

Naveen Kumar 3

623 views

Naveen Kumar 3 asked Apr 20, 2019

0 votes

0 answers

52

Peter Linz Edition 4 Exercise 7.1 Question 2 (Page No. 183)
Prove that an npda for accepting the language $L =$ { $ww^R : w ∈$ {$a, b$}$^+$ } does not accept any string not in {$ww^R$}.

Prove that an npda for accepting the language $L =$ { $ww^R : w ∈$ {$a, b$}$^+$ } does not accept any string not in {$ww^R$}.

Naveen Kumar 3

183 views

Naveen Kumar 3 asked Apr 20, 2019

1 votes

0 answers

53

Peter Linz Edition 4 Exercise 7.1 Question 1 (Page No. 183)
Find a pda with fewer than four states that accepts the language $L=${$a^nb^n:n\geq 0$} $\cup$ {$a$}.

Find a pda with fewer than four states that accepts the language $L=${$a^nb^n:n\geq 0$} $\cup$ {$a$}.

Naveen Kumar 3

340 views

Naveen Kumar 3 asked Apr 20, 2019

0 votes

0 answers

54

Peter Linz Edition 4 Exercise 6.3 Question 4 (Page No. 173)
Use the CYK method to determine if the string $w = aaabbbbab$ is in the language generated by the grammar $S → aSb|b$.

Use the CYK method to determine if the string $w = aaabbbbab$ is in the language generated by the grammar $S → aSb|b$.

Naveen Kumar 3

149 views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

0 answers

55

Peter Linz Edition 4 Exercise 6.3 Question 3 (Page No. 173)
Use the approach employed in Exercise 2 to show how the CYK membership algorithm can be made into a parsing method.

Use the approach employed in Exercise 2 to show how the CYK membership algorithm can be made into a parsing method.

Naveen Kumar 3

136 views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

0 answers

56

Peter Linz Edition 4 Exercise 6.3 Question 2 (Page No. 173)
Use the CYK algorithm to find a parsing of the string $aab$, using the grammar with productions $S\rightarrow AB,$ $A\rightarrow BB|a,$ $B\rightarrow AB|b.$

Use the CYK algorithm to find a parsing of the string $aab$, using the grammar with productions $S\rightarrow AB,$ $A\rightarrow BB|a,$ ...

Naveen Kumar 3

171 views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

0 answers

57

Peter Linz Edition 4 Exercise 6.3 Question 1 (Page No. 172)
Use the CYK algorithm to determine whether the strings $aabb, aabba,$ and $abbbb$ are in the language generated by the grammar with productions $S\rightarrow AB,$ $A\rightarrow BB|a,$ $B\rightarrow AB|b.$

Use the CYK algorithm to determine whether the strings $aabb, aabba,$ and $abbbb$ are in thelanguage generated by the grammar with productions $S\rightar...

Naveen Kumar 3

173 views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

0 answers

58

Peter Linz Edition 4 Exercise 6.2 Question 16 (Page No. 170)
“Two-standard form is general; for any context-free grammar $G$ with $λ ∉ L (G),$ there exists an equivalent grammar in two-standard form.” Prove this.

“Two-standard form is general; for any context-free grammar $G$ with $λ ∉ L (G),$ there exists an equivalent grammar in two-standard form.” Prove this.

Naveen Kumar 3

131 views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

0 answers

59

Peter Linz Edition 4 Exercise 6.2 Question 15 (Page No. 170)
A context-free grammar is said to be in two-standard form if all production rules satisfy the following pattern $A\rightarrow aBC,$ $A\rightarrow aB,$ $A\rightarrow a,$ where $A, B, C ∈ V$ and $a ∈ T$. Convert the grammar ... $S\rightarrow aSA,$ $A\rightarrow bABC,$ $B\rightarrow b,$ $C\rightarrow aBC$ into two-standard form.

A context-free grammar is said to be in two-standard form if all production rules satisfy the following pattern $A\rightarrow aBC,$ ...

Naveen Kumar 3

164 views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

1 answer

60

Peter Linz Edition 4 Exercise 6.2 Question 14 (Page No. 170)
Can every linear grammar be converted to a form in which all productions look like $A → ax,$ where $a∈ T$ and $x∈V$ $\cup$ {$\lambda$} ?

Can every linear grammar be converted to a form in which all productions look like $A → ax,$ where $a∈ T$ and $x∈V$ $\cup$ {$\lambda$} ?

Naveen Kumar 3

385 views

Naveen Kumar 3 asked Apr 19, 2019

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true