16 votes
Accepted

Mike Sipser and Wikipedia seem to disagree on Chomsky's normal form

Sipser clearly implies an or between those two rules. The two definitions say the same thing. Meanwhile, in formal language theory, it is quite common for two textbooks or article to not say the same ...
reinierpost's user avatar
  • 5,519
8 votes

Mike Sipser and Wikipedia seem to disagree on Chomsky's normal form

Sipser doesn't require that both of those forms be used. It just requires that every rule fit one of those two patterns.
D.W.'s user avatar
  • 159k
7 votes
Accepted

Are 2 independent PDAs equivalent to a turing machine?

No, such a construct can recognise at most the intersection of two context-free languages. To see where it's lacking, consider $L = \{\textsf{a}^n~|~n\in\mathbb{N}~\text{is composite}\}$. I conjecture ...
Kai's user avatar
  • 865
6 votes

Are 2 independent PDAs equivalent to a turing machine?

What you actually ask is: can language of every grammar be represented as an intersection of two context-free languages? The answer is no. To prove that, we can observe that, while the class of ...
bebidek's user avatar
  • 161
6 votes

Is there a one-state PDA that recognizes every context free language?

We have to be precise. Each context-free language can be accepted by empty stack using a push-down automaton with a single state, or by final state and two states. (In the latter case we obviously ...
Hendrik Jan's user avatar
  • 30.6k
3 votes
Accepted

A context-sensite grammar for the language of sequences of two different types of parentheses with possible intersections?

Basically, the idea is that $($ and $)$ can commute with $[$ and $]$, but $($ cannot commute with $)$ – and same for $[$ and $]$. An essentially noncontracting grammar would be: $S \to \varepsilon \...
Nathaniel's user avatar
  • 15.5k
3 votes

Are 2 independent PDAs equivalent to a turing machine?

The language $\{a^nb^nc^n | n \in \mathbb{N}\}$ belongs to a strict subset of context-sensitive languages that can be expressed in terms of an intersection of two context-free languages. Having two ...
Ṃųỻịgǻňạcểơửṩ's user avatar
2 votes

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

Based on the given definition, you cannot have a single transition that pushes multiple symbols from a single state. But you can simulate it. The idea here is to add auxiliary states and take ...
Russel's user avatar
  • 2,745
2 votes
Accepted

How PDA decide when and which state to transform to?

Quoting the same Wikipedia page (emphasis mine): If, in every situation, at most one such transition action is possible, then the automaton is called a deterministic pushdown automaton (DPDA). In ...
Ivan Smirnov's user avatar
1 vote

Not understanding example of a Pushdown Automata

the stack is kept track of by a so called "configuration". Imagine, that the configuration represents a complete description of your machine at a point in time. The transition function only ...
Knogger's user avatar
  • 1,032
1 vote

Is the Given Languages CFL or DCFL?

Your argument for $L_1$ isn't quite correct, but the core idea can indeed be adapted to obtain a deterministic pushdown automaton for $L_1$. I don't know why the answer key claims that the language is ...
Arno's user avatar
  • 3,075
1 vote

DPDA for language $L=\{a,b\}^* \setminus a^nb^n \setminus b^na^n$

Given $L=(a+b)^*- a^nb^n-b^na^n$ which could be written as $L=(a+b)^*- (a^nb^n \cup b^na^n)=(a+b)^* \bigcap (a^nb^n \cup b^na^n)^\complement= (a+b)^* \bigcap \{(a+b)^*-(a^nb^n \cup b^na^n)\}=(a+b)^*\...
1 vote
Accepted

can you read and push different symbols in a DPDA?

If you mean, you can push a symbol different from what your machine has read from the input, then yes you can. The input and stack symbols are not related and there is no rule that requires them to be ...
Russel's user avatar
  • 2,745

Only top scored, non community-wiki answers of a minimum length are eligible