The 2024 Developer Survey results are live! See the results

# Questions tagged [pushdown-automata]

Questions about state machines with a single stack for memory. They characterize the class of context-free languages.

559 questions
Filter by
Sorted by
Tagged with
175 views

### Understanding a bound for derivation length of any string in Pumping lemma for context-free languages

The following is a proof of the pumping lemma for context-free languages from Theorem 8.1 in "An Introduction to Formal Languages and Automata (6th ed.)" by Peter Linz: Let $L$ be an ...
1k views

### Pushdown Automata - can you have multiple transition functions options between 2 states?

I was wondering if you have 2 states, lets say q0 and q1. Are you allowed to have multiple options to transition between these 2 states? For example, ...
235 views

### Can PDA model Turing Complete objects if the objects' state are finite?

I am currently reading the extended Version of the Paper Online Detection of Effectively Callback Free Objects with Applications of Smart Contract. I am trying to understand the proofs of Chapter 6. ...
541 views

### PDA for equal number of as and b's where n>=1

How to design Push Down Automata for a language that has equal number of a's and b's where $n \ge 1$? I got how to do it for $n \ge 0$, not able to get it for $n \ge 1$.
80 views

### PDA for Palindrome Strings

I am studying Automaton Theory for first time and I am having problems to see if I do well some exercises and if I really finish them. For example, one exercises asks to give a PDA for all palindrome ...
1 vote
1k views

### Understanding this PDA for non-palindromes over {0,1}

I found this PDA online that accepts all non-palindromes over {0,1}. However, I can't seem to understand how it would accept, say "01011", and not accept "101101". Can someone help ...
36 views

### Should a PDA reject words not in language?

Let's say we want to construct the PDA for the following language: $$L_4 = \{w_1bw_2 | w_1, w_2 \in \{a,b,c \}^* \ and \ (\#ab\in w_1) = (2 \times \#c \in w_2)\}$$ Let's consider the following PDA ...
67 views

35 views

### Construct an NPDA for the language where the number of a's <= 3 times the number of b's

I am trying to construct an NPDA for $L = \{\omega \in \{a,b\}^* | n_a(\omega) \le 3 \times n_b(\omega)\}$. This means that for every $b$ there can be at most $3$ $a$'s So far, I understand that for ...
26 views

### Create a cfg for the language L = {w ∈ {a,b,c}* : |w| = 3na(w)}

All I know about this language is that it is equivalent to the following: $$L = \{w \in \{a,b,c\}^{∗} : n_b(w) + n_c(w) = 2 * n_a(w)\}$$ but I have absolutely no idea how to create a CFG for it.
37 views

2k views

40 views

670 views

### Show that the language $L=\{w|w$ has odd length and the middle symbol is a $0\}$ is Context-Free and construct a PDA that accepts it

Were w is any string composed over the alphabet $\Sigma = \{0,1\}$. For the first part of the exercise I've tried decomposing the problem into three different ones, mainly the first one is for the ...
45 views

### can you read and push different symbols in a DPDA?

I have an easy question about the DPDA. Could you read an input and push a different symbol to the stack. An example would be A transition from q1 to q2 where read input is v pop is epsilon(empty ...
1 vote
199 views

### Can a pushdown automaton write more than one symbols on to stack on one reading from from input tape?

The formal definition of the pushdown automata according to Mike Sisper's book on theory of computation is as follows: . The transition function however only takes in one symbol from the stack (after ...
71 views

### Equivalent context free grammar for every pushdown automaton?

Equivalent context free grammar for pushdown automata  This machine does not accept L = {a^(n)b^(n)c^(n) | n > 0} and instead accepts L = {a^(2n+1)b^(2n+1)c^(2n+1)}; also, as a side note ...
1 vote
50 views

### Simple pushdown automata question

I'm trying to derive the language it represents. However, I'm kind of new to those topics. What happens if input b is gathered once or more than one time at state q without a in the stack? It does not ...