Recent questions

0 votes

0 answers

1

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.

asked 22 hours ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 23 views

0 votes

0 answers

2

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.

asked 22 hours ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 7 views

0 votes

1 answer

3

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.

asked 22 hours ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 5 views

0 votes

0 answers

4

Peter Linz Edition 4 Exercise 7.3 Question 15 (Page No. 200)
Show that every regular language is a deterministic context-free language.

asked 22 hours ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 3 views

0 votes

0 answers

5

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.

asked 22 hours ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 6 views

0 votes

1 answer

6

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.

asked 22 hours ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 6 views

0 votes

1 answer

7

Peter Linz Edition 4 Exercise 7.3 Question 9 (Page No. 200)
Is the language {$wcw^R : w ∈ ${$a, b$}$^*$} deterministic?

asked 22 hours ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 8 views

0 votes

0 answers

8

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?

asked 22 hours ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 9 views

0 votes

0 answers

9

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

asked 22 hours ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 11 views

0 votes

0 answers

10

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.

asked 22 hours ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 2 views

0 votes

0 answers

11

Peter Linz Edition 4 Exercise 7.3 Question 4 (Page No. 200)
Is the language $L =$ {$a^nb^n : n ≥ 1$} $∪$ {$a$} deterministic?

asked 22 hours ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 5 views

0 votes

0 answers

12

Peter Linz Edition 4 Exercise 7.3 Question 3 (Page No. 200)
Is the language $L =$ {$a^nb^n : n ≥ 1$} $∪$ {$b$} deterministic?

asked 22 hours ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 3 views

0 votes

0 answers

13

Peter Linz Edition 4 Exercise 7.3 Question 2 (Page No. 200)
Show that $L =$ {$a^nb^m : m ≥ n + 2$} is deterministic.

asked 22 hours ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 2 views

0 votes

0 answers

14

Peter Linz Edition 4 Exercise 7.3 Question 1 (Page No. 200)
Show that $L =$ {$a^nb^{2n} : n ≥ 0$} is a deterministic context-free language.

asked 22 hours ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 1 view

0 votes

0 answers

15

Peter Linz Edition 4 Exercise 7.2 Question 18 (Page No. 196)
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).

asked 22 hours ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 2 views

0 votes

0 answers

16

Peter Linz Edition 4 Exercise 7.2 Question 17 (Page No. 196)
Give full details of the proof of Theorem 7.2 . Theorem 7.2 : If L = L (M) for some npda M, then L is a context-free language.

asked 22 hours ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 1 view

0 votes

0 answers

17

Peter Linz Edition 4 Exercise 7.2 Question 15 (Page No. 195)
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,λ)$}.

asked 22 hours ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 2 views

0 votes

0 answers

18

Peter Linz Edition 4 Exercise 7.2 Question 14 (Page No. 195)
find an npda for the language $L = ${ $ww^R : w ∈$ {a, b}$^+ $}

asked 22 hours ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 2 views

0 votes

0 answers

19

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)$}.

asked 23 hours ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 8 views

0 votes

1 answer

20

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

asked 1 day ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 9 views

0 votes

1 answer

21

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

asked 1 day ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 9 views

0 votes

0 answers

22

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.

asked 1 day ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 5 views

0 votes

0 answers

23

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

asked 1 day ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 4 views

0 votes

0 answers

24

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

asked 1 day ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 1 view

0 votes

0 answers

25

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

asked 1 day ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 1 view

0 votes

0 answers

26

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

asked 1 day ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 5 views

0 votes

0 answers

27

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

asked 1 day ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 2 views

0 votes

0 answers

28

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.

asked 1 day ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 1 view

0 votes

0 answers

29

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^*)$.

asked 1 day ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 1 view

0 votes

0 answers

30

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$}?

asked 1 day ago in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 2 views

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

Recent Posts

Recent Blog Comments