Recent questions and answers in Theory of Computation

0 votes

1 answer

1

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.

answered 20 hours ago in Theory of Computation by shivanisrivarshini Boss (13.7k points) | 5 views

0 votes

1 answer

2

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.

answered 21 hours ago in Theory of Computation by Satbir Boss (13.2k points) | 6 views

0 votes

1 answer

3

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

answered 21 hours ago in Theory of Computation by Satbir Boss (13.2k points) | 8 views

0 votes

0 answers

4

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

5

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

0 answers

6

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

7

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

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 23 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

+1 vote

1 answer

20

If DFA is constructed from NFA using lazy subset construction method , is it guaranteed to be the minimized DFA ?

answered 1 day ago in Theory of Computation by Ravijha (271 points) | 478 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$}.

answered 1 day ago in Theory of Computation by Ravijha (271 points) | 9 views

0 votes

1 answer

22

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

answered 1 day ago in Theory of Computation by Ravijha (271 points) | 9 views

0 votes

0 answers

23

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

24

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

25

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

26

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

27

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

28

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

29

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

30

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

31

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

0 votes

0 answers

32

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

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

0 votes

0 answers

33

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

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

0 votes

2 answers

34

Ullman (TOC) Edition 3 Exercise 2.2.6 Problem 2.2.11 (Page No. 54)

answered 3 days ago in Theory of Computation by Ravijha (271 points) | 27 views

0 votes

4 answers

35

Regular Expression
Can I write a* + b* = (a + b)* ????

answered 3 days ago in Theory of Computation by Ravijha (271 points) | 174 views

0 votes

3 answers

36

Nfa dfa toc ace 1

answered 3 days ago in Theory of Computation by Ravijha (271 points) | 68 views

0 votes

2 answers

37

States in DFA
If NFA has 'n' states then how DFA can have 2^n states. Please help me in understanding how this is true. As per my understanding every DFA is NFA then how no of states can be more in DFA than nfa Please suggest Thanks

answered 3 days ago in Theory of Computation by Ravijha (271 points) | 66 views

+1 vote

2 answers

38

Self Doubt TOC Enumeration Method
If language L is countable infinite set then, L is Recursive as we can define enumeration method for the countable set. or It can Regular ??

answered 3 days ago in Theory of Computation by Ravijha (271 points) | 159 views

0 votes

1 answer

39

Self Doubt:Toc

answered 3 days ago in Theory of Computation by Ravijha (271 points) | 40 views

0 votes

1 answer

40

Michael Sipser Edition 3 Exercise 1 Question 60 (Page No. 92)
Let $Σ = \{a, b\}.$ For each $k\geq 1,$ let $C_{k}$ be the language consisting of all strings that contain an a exactly $k$ places from the right-hand end$.$ Thus $C_{k}=\sum^{*}a\sum^{k-1}.$ Describe an $\text{NFA}$ with $k + 1$ states that recognizes $C_{k}$ in terms of both a state diagram and a formal description$.$

answered 6 days ago in Theory of Computation by aditi19 Active (3.7k points) | 20 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 questions and answers in Theory of Computation

Recent Posts

Recent Blog Comments