# Questions tagged [pushdown-automata]

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

387 questions
Filter by
Sorted by
Tagged with
588 views

501 views

### Algorithm to detect if word belongs to pushdown automaton

I am creating a simple program to detect if the given pushdown automaton accepts the given word, and I have a problem in finding an algorithm that does that. My thought at first would be to go ...
268 views

### How to represent a double push or double pop operation in push down automata

I want to know the theoretical representation of a double push or a double pop in pda
3k views

### Push down automata acceptance by Empty stack and final state

I have a very basic question. Can we have a PDA which can accept a string by both final states and empty stack? Can the same PDA accept by the two modes simultaneously ? If there are final states ...
1k views

### PDA for { xy : |x| = |y|, x ≠ y} from its grammar, and intuition behind it

I know the grammar for the language $\{ xy : |x| = |y|, x ≠ y \}$ if $\Sigma=\{a,b\}$: \begin{align*} &S→AB∣BA \\ &A→a∣aAa∣aAb∣bAa∣bAb \\ &B→b∣aBa∣aBb∣bBa∣bBb \end{align*} I ...
78 views

1k views

### Determine whether a context-free language is deterministic or not

I define language $L = \{a^k a^m b^m c^k \} \cup \{a^n b^n b^k c^k\}$ and I want to determine if it's deterministic context free language or it is nondeterministic. so I tried to create pushdown ...
809 views

### Conversion from nondeterministic PDA to deterministic PDA

Why is the conversion from nondeterministic PDA to deterministic PDA not possible?
343 views

### How to understand pushdown automata intuitively?

What is an intuitive way of understanding what a push down automaton is capable of computing?
51k views

### Difference between DPDA and NPDA?

What are the major differences between Deterministic Push Down Automata and Non-deterministic Push Down Automata? Which one is faster and how? Also what are the drawbacks of DPDA with respect to NPDA. ...
I had a homework assignment where I had to build a PDA over the alphabet $\{a,b\}^*$, accepting $L = \{x \mid x \text{ is even but not a palindrome}\}$. I already turned it in, but I know I had it ...