Dark Mode

Recent questions tagged pushdown-automata

0 votes

1 answer

1

Context Free Languages
Is the following language CFL : { ww | w in (a+b)* and |w| <1000 }

practicalmetal asked in Theory of Computation Mar 21

by practicalmetal

178 views

0 votes

1 answer

2

Context Free Languages
Is the following language context free: The set of all strings with number of a’s equal to number of b’s and the sum of a’s and b’s to be divisible by 3.

practicalmetal asked in Theory of Computation Mar 16

by practicalmetal

175 views

2 votes

2 answers

3

GATE CSE 2023 | Question: 30
Consider the pushdown automaton $\text{(PDA)}\;P$ below, which runs on the input alphabet $\{a, b\}$, has stack alphabet $\{\perp, A\}$, and has three states $\{s, p, q\}$, with $s$ being the start state. A transition from state $u$ to state $v$ ... $\left.0 \leq n\right\}$ $\left\{a^{m} \mid 0 \leq m\right\} \cup\left\{b^{n} \mid 0 \leq n\right\}$

admin asked in Theory of Computation Feb 15

by admin

1.3k views

0 votes

0 answers

4

Context Free Languages(CFG) Push Down Anutomata(PDA)
PDA for $a^i b^j | i \neq 2j+1$ ?

jaisyking asked in Theory of Computation Jan 12

63 views

0 votes

1 answer

5

Construct pushdown automata that recognize the following language. L= (a²ⁿ b³ⁿ | n ≥ 0}
Construct pushdown automata that recognize the following language. L= (a²ⁿ b³ⁿ | n ≥ 0}

M_Umair_Khan42900 asked in Theory of Computation Dec 29, 2022

by M_Umair_Khan42900

113 views

0 votes

1 answer

6

Write regular expression to denote a language L a) String which begin or end with either 00 or 11. b) The set of all strings, when viewed as binary representation of integers, that are divisible by 2. c) The set of all strings containing 00. d) String not containing the substring 110.

M_Umair_Khan42900 asked in Theory of Computation Dec 29, 2022

by M_Umair_Khan42900

394 views

2 votes

0 answers

7

Is it CFL or CSL?
Is {$a^nb^nc^n$ | $n>=0$} CSL? After comparing both a and b, stack would be empty. So it can’t be CFL. So it is CSL or recursive. And does this language require more than 1 stack? Please tell how would check for the grammer of this language even if it is in CSL. Thank you

h4kr asked in Theory of Computation Dec 23, 2022

by h4kr

116 views

0 votes

1 answer

8

Push Down Automation | Parsing | Input Buffer and Stack
Consider a situation, where the input buffer is still having elements, and our PDA has reached final state. Given that for next input element the final state has no transition defined. In above situation will the i/p string be ... in all cases May be accepted if empty stack acceptance is allowed in the given PDA Something else, I can explain

Souvik33 asked in Compiler Design Dec 20, 2022

125 views

1 vote

1 answer

9

Autometa | PDA
Consider the following Language: L= $a^{n}b^{n}c^{n}$ | $n \geq 0$ Consider the following Statement: A PDA can accept the given language. As we can insert 2 a’s for every entry of a, and pop one ‘a’ for every b and after all b’s, pop one ‘a’ for every entry of ‘c’ So the above language is a CFL. Prove the above statement WRONG

Souvik33 asked in Theory of Computation Nov 26, 2022

197 views

0 votes

1 answer

10

[email protected] Test Series 2022
Please explain with simplified diagram the transition in the pda. Ans (d)

SKMAKM asked in Theory of Computation Jul 18, 2022

by SKMAKM

183 views

1 vote

2 answers

11

DCFL - TOC
Is the following language a DCFL? Please explain your reasoning.

atulcse asked in Theory of Computation Jan 21, 2022

449 views

19 votes

2 answers

12

GATE CSE 2021 Set 1 | Question: 51
In a pushdown automaton $P=(Q, \Sigma, \Gamma, \delta, q_0, F)$, a transition of the form, where $p,q \in Q$, $a \in \Sigma \cup \{ \epsilon \}$, and $X,Y \in \Gamma \cup \{ \epsilon \}$ ... $\Gamma = \{ \#, A\}$. The number of strings of length $100$ accepted by the above pushdown automaton is ___________

Arjun asked in Theory of Computation Feb 18, 2021

by Arjun

6.9k views

2 votes

2 answers

13

NIELIT 2017 DEC Scientist B - Section B: 57
Which machine is equally powerful in both deterministic and non-deterministic form? Push Down Automata Turing machine Linear Bounded Automata None of the options

Lakshman Bhaiya asked in Theory of Computation Mar 30, 2020

by Lakshman Bhaiya

1.2k views

1 vote

2 answers

14

Michael Sipser Edition 3 Exercise 5 Question 33 (Page No. 241)
Consider the problem of determining whether a $PDA$ accepts some string of the form $\{ww \mid w \in \{0,1\}^{\ast} \}$ . Use the computation history method to show that this problem is undecidable.

Lakshman Bhaiya asked in Theory of Computation Oct 20, 2019

by Lakshman Bhaiya

435 views

0 votes

0 answers

15

Michael Sipser Edition 3 Exercise 4 Question 24 (Page No. 212)
A useless state in a pushdown automaton is never entered on any input string. Consider the problem of determining whether a pushdown automaton has any useless states. Formulate this problem as a language and show that it is decidable.

Lakshman Bhaiya asked in Theory of Computation Oct 17, 2019

by Lakshman Bhaiya

357 views

0 votes

0 answers

16

Michael Sipser Edition 3 Exercise 3 Question 9 (Page No. 188)
Let a $k-PDA$ be a pushdown automaton that has $k$ stacks. Thus a $0-PDA$ is an $NFA$ and a $1-PDA$ is a conventional $PDA$. You already know that $1-PDAs$ are more powerful (recognize a larger class of languages) than ... $3-PDAs$ are not more powerful than $2-PDAs$. (Hint: Simulate a Turing machine tape with two stacks.)

Lakshman Bhaiya asked in Theory of Computation Oct 15, 2019

by Lakshman Bhaiya

214 views

1 vote

0 answers

17

Michael Sipser Edition 3 Exercise 2 Question 47 (Page No. 159)
Let $\Sigma = \{0,1\}$ and let $B$ be the collection of strings that contain at least one $1$ in their second half. In other words, $B = \{uv \mid u \in \Sigma^{\ast}, v \in \Sigma^{\ast}1\Sigma^{\ast}\: \text{and} \mid u \mid \geq \mid v \mid \}$. Give a PDA that recognizes $B$. Give a CFG that generates $B$.

Lakshman Bhaiya asked in Theory of Computation Oct 13, 2019

by Lakshman Bhaiya

642 views

0 votes

0 answers

18

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

248 views

0 votes

0 answers

19

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

233 views

0 votes

0 answers

20

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

244 views

0 votes

0 answers

21

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

236 views

0 votes

0 answers

22

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

306 views

1 vote

1 answer

23

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

339 views

Page:

1
2
3
4
5
6
...
8
next »

Recent questions tagged pushdown-automata