Dark Mode

Recent questions tagged npda

0 votes

0 answers

1

PDA | TOC | Practice Question
Identify the type of the given language and draw the corresponding automata for the language. $L=\left \{a^{i}b^{j}c^{k} \space\ | \space\ j=max(i,k) \right \}$ A] Regular B] DCFL C] CFL but not DCFL D] Non-CFL Please describe your selection.

anupamsworld asked in Theory of Computation Sep 2

by anupamsworld

124 views

0 votes

0 answers

2

PDA | TOC | Practice Question | Unacademy Class
Construct PDA using empty stack method for the given language. $L=\left \{ x \space\ | \space\ x\in \left \{ a,b \right \}^{*} ; n_{a}(x) >= n_{b}(x) \right \}$ //number of a’s is greater than or equal to number of b’s

anupamsworld asked in Theory of Computation Sep 1

by anupamsworld

69 views

1 vote

1 answer

3

Applied Test Series
The language accepted by the given PDA is

LRU asked in Theory of Computation Oct 3, 2021

by LRU

184 views

0 votes

2 answers

4

NIELIT 2017 DEC Scientific Assistant A - Section B: 6
Which of the following statements is true ? Melay and Moore machines are language acceptors. Finite State automata is language translator. NPDA is more powerful than DPDA. Melay machine is more powerful than Moore machine.

Lakshman Patel RJIT asked in Theory of Computation Mar 31, 2020

by Lakshman Patel RJIT

717 views

0 votes

6 answers

5

NIELIT 2017 DEC Scientist B - Section B: 39
Which of the following is true? Mealy and Moore machine are language acceptors. Finite State automata is language translator. NPDA is more powerful than DPDA. Melay machine is more powerful than Moore machine.

Lakshman Patel RJIT asked in Theory of Computation Mar 30, 2020

by Lakshman Patel RJIT

4.8k views

0 votes

0 answers

6

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

Naveen Kumar 3 asked in Theory of Computation Jun 23, 2019

by Naveen Kumar 3

200 views

0 votes

0 answers

7

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.

Naveen Kumar 3 asked in Theory of Computation Jun 23, 2019

by Naveen Kumar 3

199 views

0 votes

0 answers

8

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

Naveen Kumar 3 asked in Theory of Computation Jun 23, 2019

by Naveen Kumar 3

220 views

0 votes

0 answers

9

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

Naveen Kumar 3 asked in Theory of Computation Jun 23, 2019

by Naveen Kumar 3

205 views

0 votes

0 answers

10

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

Naveen Kumar 3 asked in Theory of Computation Jun 23, 2019

by Naveen Kumar 3

238 views

1 vote

1 answer

11

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

Naveen Kumar 3 asked in Theory of Computation Jun 22, 2019

by Naveen Kumar 3

293 views

1 vote

2 answers

12

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

Naveen Kumar 3 asked in Theory of Computation Jun 22, 2019

by Naveen Kumar 3

917 views

0 votes

0 answers

13

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.

Naveen Kumar 3 asked in Theory of Computation Jun 22, 2019

by Naveen Kumar 3

164 views

0 votes

0 answers

14

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

Naveen Kumar 3 asked in Theory of Computation Jun 22, 2019

by Naveen Kumar 3

167 views

0 votes

1 answer

15

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

Naveen Kumar 3 asked in Theory of Computation Jun 22, 2019

by Naveen Kumar 3

215 views

0 votes

0 answers

16

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

Naveen Kumar 3 asked in Theory of Computation Jun 22, 2019

by Naveen Kumar 3

141 views

0 votes

0 answers

17

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.

Naveen Kumar 3 asked in Theory of Computation Jun 22, 2019

by Naveen Kumar 3

533 views

0 votes

0 answers

18

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

Naveen Kumar 3 asked in Theory of Computation Jun 22, 2019

by Naveen Kumar 3

190 views

0 votes

0 answers

19

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

Naveen Kumar 3 asked in Theory of Computation Jun 22, 2019

by Naveen Kumar 3

121 views

0 votes

0 answers

20

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

Naveen Kumar 3 asked in Theory of Computation Jun 22, 2019

by Naveen Kumar 3

157 views

0 votes

0 answers

21

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

Naveen Kumar 3 asked in Theory of Computation Jun 22, 2019

by Naveen Kumar 3

151 views

0 votes

1 answer

22

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

Naveen Kumar 3 asked in Theory of Computation Apr 20, 2019

by Naveen Kumar 3

338 views

0 votes

0 answers

23

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

Naveen Kumar 3 asked in Theory of Computation Apr 20, 2019

by Naveen Kumar 3

261 views

0 votes

0 answers

24

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.

Naveen Kumar 3 asked in Theory of Computation Apr 20, 2019

by Naveen Kumar 3

164 views

0 votes

0 answers

25

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

Naveen Kumar 3 asked in Theory of Computation Apr 20, 2019

by Naveen Kumar 3

211 views

0 votes

0 answers

26

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

Naveen Kumar 3 asked in Theory of Computation Apr 20, 2019

by Naveen Kumar 3

144 views

0 votes

0 answers

27

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 =$ ... $L =$ {$w : n_a (w) + n_b (w) = n_c (w)$}. (j) here. (k) $L =$ {$w : n_a (w) < n_b (w)$}.

Naveen Kumar 3 asked in Theory of Computation Apr 20, 2019

by Naveen Kumar 3

233 views

1 vote

0 answers

28

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)

Naveen Kumar 3 asked in Theory of Computation Apr 20, 2019

by Naveen Kumar 3

372 views

0 votes

0 answers

29

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

Naveen Kumar 3 asked in Theory of Computation Apr 20, 2019

by Naveen Kumar 3

117 views

0 votes

1 answer

30

TESTBOOK TEST SERIES
WHAT WILL BE THE ANS?

Avik Chowdhury asked in Theory of Computation Oct 3, 2018

by Avik Chowdhury

151 views

Page:

Recent questions tagged npda