Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions tagged pushdown-automata
5
votes
2
answers
211
Context free or not ?
$L = \{ a^i b^j c^k d^l \mid i+k=j+l \}$ Is L context free? If yes, then draw PDA. If no, why?
anonymous
asked
in
Theory of Computation
Aug 22, 2015
by
anonymous
3.8k
views
context-free-language
pushdown-automata
2
votes
3
answers
212
plz answer
the minimum number of states in the PDA accepting the language $L=\left\{a^n b^m \mid n>m;m,n>0 \right\}$ a) 2 b) 3 c) 4 d) 5
shreshtha5
asked
in
Theory of Computation
Apr 26, 2015
by
shreshtha5
2.9k
views
theory-of-computation
pushdown-automata
82
votes
4
answers
213
GATE CSE 2015 Set 1 | Question: 51
Consider the NPDA ... follows: Which one of the following sequences must follow the string $101100$ so that the overall string is accepted by the automaton? $10110$ $10010$ $01010$ $01001$
makhdoom ghaya
asked
in
Theory of Computation
Feb 13, 2015
by
makhdoom ghaya
23.7k
views
gatecse-2015-set1
theory-of-computation
pushdown-automata
normal
1
vote
1
answer
214
Language accepted by PDA is __________?
Vikrant Singh
asked
in
Theory of Computation
Jan 27, 2015
by
Vikrant Singh
2.1k
views
pushdown-automata
theory-of-computation
13
votes
2
answers
215
How to draw NPDA for language L = { a^i b^j c^m | m >= min( i,j) }
L1 = { a^i b^j c^m | m ≥ min(i,j) } L2 = { a^i b^j c^m | m ≥ max(i,j) } Which language is CFL ? ANS : L1 is CFL but L2 is NOT. My understanding : For Language L1 : ( Here I am interested in ... above NPDA is right , then we can construct NPDA for L2 also. But Answer part saying L2 is not CFL. So above NPDA is right or wrong ??
tushark
asked
in
Theory of Computation
Nov 5, 2014
by
tushark
4.0k
views
theory-of-computation
finite-automata
pushdown-automata
66
votes
5
answers
216
GATE IT 2005 | Question: 38
Let $P$ be a non-deterministic push-down automaton (NPDA) with exactly one state, $q$, and exactly one symbol, $Z$, in its stack alphabet. State $q$ is both the starting as well as the accepting state of the PDA. The stack is initialized with one $Z$ before the start of ... $L(P)$ and $N(P)$ are necessarily $Σ^*$. Neither $L(P)$ nor $N(P)$ are necessarily $Σ^*$
Ishrat Jahan
asked
in
Theory of Computation
Nov 3, 2014
by
Ishrat Jahan
12.3k
views
gateit-2005
theory-of-computation
pushdown-automata
normal
55
votes
9
answers
217
GATE IT 2004 | Question: 40
Let $M = (K, Σ, Г, Δ, s, F)$ be a pushdown automaton, where $K = (s, f), F = \{f\}, \Sigma = \{a, b\}, Г = \{a\}$ and $Δ = \{((s, a, \epsilon), (s, a)), ((s, b, \epsilon), (s, a)), (( s, a, a), (f, \epsilon)), ((f, a, a), (f, \epsilon)), ((f, b, a), (f, \epsilon))\}$. Which one of the following strings is not a member of $L(M)$? $aaa$ $aabab$ $baaba$ $bab$
Ishrat Jahan
asked
in
Theory of Computation
Nov 2, 2014
by
Ishrat Jahan
37.5k
views
gateit-2004
theory-of-computation
pushdown-automata
normal
30
votes
4
answers
218
GATE IT 2006 | Question: 33
Consider the pushdown automaton (PDA) below which runs over the input alphabet $(a, b, c)$. It has the stack alphabet $\{Z_0, X\}$ where $Z_0$ is the bottom-of-stack marker. The set of states of the PDA is $(s, t, u, f\}$ where $s$ is the start state and $f$ is the final state. The PDA ... $\{a^lb^mc^n \mid 2l = m + n\}$ $\{a^lb^mc^n \mid m = n\}$
Ishrat Jahan
asked
in
Theory of Computation
Oct 31, 2014
by
Ishrat Jahan
7.5k
views
gateit-2006
theory-of-computation
pushdown-automata
normal
32
votes
3
answers
219
GATE IT 2006 | Question: 31
Which of the following languages is accepted by a non-deterministic pushdown automaton (PDA) but NOT by a deterministic PDA? $\{a^nb^nc^n \mid n ≥ 0\}$ $\{a^lb^mc^n \mid l ≠ m \text{ or } m ≠ n\}$ $\{a^nb^n \mid n ≥ 0\}$ $\{a^mb^n \mid m, n ≥ 0\}$
Ishrat Jahan
asked
in
Theory of Computation
Oct 31, 2014
by
Ishrat Jahan
17.9k
views
gateit-2006
theory-of-computation
pushdown-automata
normal
17
votes
2
answers
220
GATE CSE 1996 | Question: 13
Let $Q=\left( \left\{q_1,q_2 \right\}, \left\{a,b\right \}, \left\{a,b,\bot \right\}, \delta, \bot, \phi \right)$ ... $\delta(q_2,b,b) = \left\{(q_2, \epsilon)\right\}$ $\delta(q_2,\epsilon,\bot) = \left\{(q_2, \epsilon)\right\}$
Kathleen
asked
in
Theory of Computation
Oct 9, 2014
by
Kathleen
5.6k
views
gate1996
theory-of-computation
pushdown-automata
normal
descriptive
25
votes
4
answers
221
GATE CSE 1997 | Question: 6.6
Which of the following languages over $\left\{a,b,c\right\}$ is accepted by a deterministic pushdown automata? $\left\{ wcw^R \mid w \in \left\{a,b\right\}^*\right\}$ $\left\{ ww^R \mid w \in \{a,b,c\}^*\right\}$ ... $w^R$ is the string obtained by reversing $'w'$.
Kathleen
asked
in
Theory of Computation
Sep 29, 2014
by
Kathleen
10.6k
views
gate1997
theory-of-computation
pushdown-automata
easy
30
votes
1
answer
222
GATE CSE 1998 | Question: 13
Let $M=(\{q_0, q_1\}, \{0, 1\}, \{z_0, X\}, \delta, q_0, z_0, \phi)$ be a Pushdown automation where $\delta$ is given by $\delta(q_0, 1, z_0) = \{(q_0, Xz_0)\}$ $\delta(q_0, \epsilon, z_0) = \{(q_0, \epsilon)\}$ ... $\delta(q_0, 0, z_0) = \{(q_0, z_0)\}$ What is the language accepted by this PDA by empty stack? Describe informally the working of the PDA
Kathleen
asked
in
Theory of Computation
Sep 26, 2014
by
Kathleen
6.1k
views
gate1998
theory-of-computation
pushdown-automata
descriptive
45
votes
6
answers
223
GATE CSE 2009 | Question: 16, ISRO2017-12
Which one of the following is FALSE? There is a unique minimal DFA for every regular language Every NFA can be converted to an equivalent PDA. Complement of every context-free language is recursive. Every nondeterministic PDA can be converted to an equivalent deterministic PDA.
Kathleen
asked
in
Theory of Computation
Sep 22, 2014
by
Kathleen
15.6k
views
gatecse-2009
theory-of-computation
easy
isro2017
pushdown-automata
18
votes
2
answers
224
GATE CSE 2001 | Question: 6
Give a deterministic PDA for the language $L=\{a^ncb^{2n} \mid n \geq 1\}$ over the alphabet $\Sigma = \{a,b,c\}$. Specify the acceptance state.
Kathleen
asked
in
Theory of Computation
Sep 14, 2014
by
Kathleen
5.0k
views
gatecse-2001
theory-of-computation
normal
pushdown-automata
descriptive
27
votes
4
answers
225
GATE CSE 2000 | Question: 8
A push down automation (pda) is given in the following extended notation of finite state diagram: The nodes denote the states while the edges denote the moves of the pda. The edge labels are of the form $d$, $s/s'$ where $d$ ... the above notation that accept the language $\left\{0^{n}1^{m} \mid n \leq m \leq 2n\right\}$ by empty stack
Kathleen
asked
in
Theory of Computation
Sep 14, 2014
by
Kathleen
5.1k
views
gatecse-2000
theory-of-computation
descriptive
pushdown-automata
57
votes
1
answer
226
GATE CSE 1999 | Question: 1.6
Let $L_1$ be the set of all languages accepted by a PDA by final state and $L_2$ the set of all languages accepted by empty stack. Which of the following is true? $L_1 = L_2$ $L_1 \supset L_2$ $L_1 \subset L_2$ None
Keith Kr
asked
in
Theory of Computation
Sep 10, 2014
by
Keith Kr
21.9k
views
normal
theory-of-computation
gate1999
pushdown-automata
Page:
« prev
1
...
3
4
5
6
7
8
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
Quick search syntax
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
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(684)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
244k
comments
80.0k
users
Recent questions tagged pushdown-automata
Recent Blog Comments
category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...