GATEBOOK

krmanish043 asked Dec 25, 2018

463 views

0 votes

Which of the following is correct statement?

DPDA and NPDA have the same powers.
An NFA with 1 Stack is NOT equivalent to NPDA.
DPDA with final state acceptance has the same power as DPDA with empty stack acceptance
NPDA with final state acceptance has the same power as NPDA with empty stack acceptance

krmanish043 asked Dec 25, 2018

krmanish043

463 views

See all

0 Please log in or register to add a comment.

Please log in or register to answer this question.

1 Answer

0 votes

Answer is 4.

https://nptel.ac.in/courses/Webcourse-contents/IIT-%20Guwahati/afl/modules/module-8/lecture-2/topic-1/slides/s13.htm

prashant jha 1 answered Dec 25, 2018

prashant jha 1

See all

1 1 comment

krmanish043

commented Dec 25, 2018

THANKS BUDDY

0 votes

Please log in or register to add a comment.

Voting & Accepting an answer helps improve the community

← Previous Next →

← Previous in category Next in category →

Related questions

0 votes

0 answers

krmanish043 asked Dec 25, 2018

208 views

GATEBOOK
Consider a PDA P=({q},{0,1},{0,1,Z0},T,Q,Z0,{p})P=({q},{0,1},{0,1,Z0},T,Q,Z0,{p}), where TT consists of the transitions δ(q,0,Z0)={(q,0Z0)}δ(q,0,Z0)={(q,0Z0)} δ(q,1,Z0)={(q,1Z0)}δ(q,1,Z0)={(q,1Z0)} ... PDA is {0n1n∣n≥0}{0n1n∣n≥0} All palindromes with over 00's and 11's All the strings with equal number of 00's and 11's All the strings with more 00's then 11's

Consider a PDA P=({q},{0,1},{0,1,Z0},T,Q,Z0,{p})P=({q},{0,1},{0,1,Z0},T,Q,Z0,{p}), where TT consists of the transitionsδ(q,0,Z0)={(q,0Z0)}δ(q,0,Z0)={(q,0Z0)}δ(q,1,Z0)=...

krmanish043

208 views

krmanish043 asked Dec 25, 2018

0 votes

0 answers

Kuldeep Pal asked Dec 3, 2017

201 views

gatebook
Let L be any a language over input alphabet {0,1}, and T(L) can be formed by applying following 2 rules 1. Adding odd number of in the beginning and odd number of at the end, if the string is of odd length 2. Removing odd number of from the beginning if the string is ... B. T(L) is always CFL, but need not be regular C. T(L) can never be a regular language D. Cant say anything about T(L)

Let L be any a language over input alphabet {0,1}, and T(L) can be formed by applying following 2 rules1. Adding odd number of in the beginning and odd number of at the...

Kuldeep Pal

201 views

Kuldeep Pal asked Dec 3, 2017

Theory of Computation
theory-of-computation

+ –

0 votes

0 answers

Kuldeep Pal asked Dec 3, 2017

259 views

gatebook
Time complexity to find a string of length k is accepted by a given deterministic finite automata on n states, over 2 symbol input alphabet is A. O(k) B. O(nk) C. O(klogn) D. None

Time complexity to find a string of length k is accepted by a given deterministic finite automata on n states, over 2 symbol input alphabet isA. O(k)B. O(nk)C. O(klogn)D....

Kuldeep Pal

259 views

Kuldeep Pal asked Dec 3, 2017

Theory of Computation
theory-of-computation

+ –

0 votes

1 answer

Kuldeep Pal asked Dec 3, 2017

393 views

gatebook
Consider the DFA with states {0,1,2,3,4}, input alphabet {0.1}, start state 0, final state 0, and the transition function This DFA accepts? A. Set of binary strings containing even number of 0’s B. Set of binary strings containing odd number of 0’s C. Set of binary strings containing even number of 1’s D. Set of binary strings containing odd number of 1’s

Consider the DFA with states {0,1,2,3,4}, input alphabet {0.1}, start state 0, final state 0, andthe transition function This DFA accepts?A. Set of binary strings contain...

Kuldeep Pal

393 views

Kuldeep Pal asked Dec 3, 2017

Theory of Computation
theory-of-computation

+ –

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

0 reply

Please log in or register to add a comment.

Please log in or register to answer this question.

1 Answer

1 1 comment reply

Please log in or register to add a comment.

Related questions

0

1 1 comment