Recent questions tagged npda

0 votes

1 answer

1

TESTBOOK TEST SERIES
WHAT WILL BE THE ANS?

asked Oct 3 in Theory of Computation by Avik Chowdhury Junior (827 points) | 29 views

0 votes

0 answers

2

Existence of a 2 state NPDA
How can we convert an arbitrary NPDA into an NPDA with at most 2 states? I know the existence of a 3 state PDA, but how can it be done by using just 2 states?

asked Jul 15 in Theory of Computation by Lakshay Kakkar Active (1.2k points) | 20 views

+1 vote

2 answers

3

#Test series
Q. {al bm cn | l ≠ m or m ≠ n} construct a PDA for this language?

asked Jul 10 in Theory of Computation by himgta Active (1.7k points) | 41 views

0 votes

1 answer

4

Introduction to Computer Theory
Draw PDA for ((a^m)(b^n)(a^n)(b^m)) ?

asked Apr 13 in Theory of Computation by The Capricorn (147 points) | 54 views

+4 votes

0 answers

5

Introduction to Computer Theory
Construct a PDA for the language of all those strings in which the number of $b 's$ is double the number of $a 's$. $a$ and $b$ can occur in any order. For example: $L=\{\text{^}, abb, bab, bba, aabbbb, ababbb, abbbabb, abbbab, abbba, ...... \}$

asked Mar 28 in Theory of Computation by The Capricorn (147 points) | 166 views

0 votes

0 answers

6

Construct a NPDA (peter linz) Exercise 7.2.6

asked Mar 25 in Theory of Computation by Mk Utkarsh Boss (19.8k points) | 137 views

+2 votes

1 answer

7

Power of Pushdown Machines
Which is more powerful :- 2-way Non-Deterministic Pushdown Machine(NDPDM) or 2-way Deterministic Pushdown Machine(DPDM) ? (or) Do both machine models have the same power ?

asked Mar 4 in Theory of Computation by ankitgupta.1729 Loyal (7.6k points) | 47 views

0 votes

0 answers

8

Non-Deterministic PDA
I'm getting its equaltion {anbn | n > 0} U {a} U {b} But given is {anbn | n >= 0} U {a} U {b} Whether epsilon is accepted or not??

asked Dec 24, 2017 in Theory of Computation by Ashwin Kulkarni Boss (17.9k points) | 120 views

+1 vote

2 answers

9

Arrange in the increasing order of power of following automata-

asked Dec 11, 2017 in Theory of Computation by Durgesh Singh Junior (887 points) | 142 views

+1 vote

0 answers

10

made easy test series
The language {w| the length of w is odd and it's middle symbol is 0, Wε(0+1)*} Why do we need a PDA for above language. I don't think we need a PDA for this language. I wrote the following RE. Tell me whats wrong in it:- [(0+1)(0+1)(0+1)]+0[(0+1)(0+1)(0+1)]+ + (other small left over strings like 0,101,100,001,000..... which are not covered in first part of expression)

asked Nov 29, 2017 in Theory of Computation by ♥_Less Active (1k points) | 87 views

0 votes

0 answers

11

Practice question #4
Consider the machines, M1 - a NPDA accepting L1, M2 - a 2 way PDA accepting L2, M3 - a PDA with two stacks accepting L3. Choose the false statement, 1) For any CFL L, there exists some M1, M2 and M3. 2) For some CSL L, there exists some M1,M2 and M3. 3) For every recursive set, there exists some M1,M2 and M3. 4) The power of the machines are not M1 <= M2 < M3.

asked Sep 18, 2017 in Theory of Computation by AnilGoudar Active (4.6k points) | 78 views

+1 vote

1 answer

12

TOC DPDA vs NPDA
How many stacks are available with DPDA and NPDA? I assume it is 1 with DPDA and n with NPDA where n is some constant. Assume i have a language ,over alphabet a,b,c,dL=( W |n(a)=n(b) and n(c)=n(d) ),where n(a) is number if a in words. It is a CFL. Now can DPA handle this ?If yes,then how?If not,then why?

asked Jul 31, 2017 in Theory of Computation by rahul sharma 5 Boss (25k points) | 533 views

+1 vote

1 answer

13

Peter Linz Exercise 7.1
Q1) Given, $L1 = (aaa^*b)$ $L2 = (aab^*aba^*)$ Find the union of $L1$ and $L2$, and also find $L1 - L2$. Q2) Find the npda's of the following: 1) $L = \{ a^nb^m :n \leq m \leq 3n\}$ 2) $L = \{w : 2n_a(w) \leq n_b(w)) \leq 3n_a(w) \}$.

asked Jul 8, 2017 in Theory of Computation by Shubhanshu Boss (15.5k points) | 133 views

0 votes

1 answer

14

NPDA and DPDA
Can we make NPDA? L= {anbn| n>=0,a,b are input variables} if yes then make it .

asked Jul 6, 2017 in Theory of Computation by akankshadewangan24 Active (4.2k points) | 254 views

+2 votes

0 answers

15

How to construct npda for given languages (Peter Linz 3rd Ed, Exercise 7, Ques 4)?

asked Apr 30, 2017 in Theory of Computation by Vishal Goel Active (1.5k points) | 221 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 tagged npda

Recent Posts

Recent Blog Comments