# Tagged Questions

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

40 views

### I can't understand this example of PDA Automata

looking for old tests of Language Theory, I see this exercise: Give a PDA automata that recognize the language $L = \{w \in \{a,b\}^*,\ 2|w|_a=3|w|_b\}$ They propose this solution: Can anyone help ...
55 views

33 views

### Language involving length constraints and reversal

Why is the language $A=\{wtw^r: w,t\in\{0,1\}^*\text{ and }|w|=|t|\}$ not a context free language? It is turning out to be really tricky. Is there an easy way to show this?
60 views

### How to design a PDA for the language of words with s a's, t b's and s⋅t c's? [closed]

I have the language $\qquad L=\{ a^s b^t c^m \mid s,t,m \; \in \; \mathbb{N^{+}} \text{ and } t<4, s \cdot t=m\}$. How do I go about designing a PDA for it ? I can't figure out a way to deal ...
222 views

### Formal construction of PDA intersecting a DFA

Given the PDA $P = (Q_P,\Sigma,\Gamma_P,\delta_P,F_P)$ and the DFA $D = (Q_D, \Sigma, \delta_D,q_D,F_D)$ What is the 6-tuple definition of the PDA such that: $L(P') = L(P) \cap L(D)$ I don't ...
397 views

### Is non-determinism in a non-deterministic turing machine different from that of finite automata and push down automata?

Let a input string be given as $w_1w_2...w_n$. Then if a NFA is currently in state $r$ ( and has read the input upto alphabet $w_i$ ) then before reading the next input symbol the NFA splits into two ...
66 views

### When does a PDA split?

In case of NFA, if the NFA is in a state and reads $\epsilon$ ( empty string ) the NFA splits in to two, with one being at the current state and other with the state along the $\epsilon$ transition. ...
103 views

### How powerful is a k-stack pushdown automaton with a unary stack alphabet?

I'm interested in pushdown automata with a unary stack alphabet: let's call them UPDA's. Define a $k$-UPDA to be a pushdown automaton with $k$ stacks, each with a unary stack alphabet. I've figured ...
224 views