6
The short (and not very useful) answer is that we can prove that PDA equivalence is undecidable, and we can prove that DFA equivalence is decidable.
It is important to realize that formally, the above is the only mathematically valid "reason". What you are asking is more about the intuition for this result.
The fact that there are infinitely many ...
3
Hint: replace every $d$-depth transition with a set of states and transitions that will read out $d-1$ elements, then read the last element and do the transition, and afterwards return the last $d-1$ elements back to the stack.
Another hint: to "remember" the $d-1$ elements, construct a unique "path" for each unique combination of the $d-...
3
Here is the idea in a nutshell:
Given a Turing machine $M$, we can construct a context-free grammar $G$ such that if $M$ halts then $\overline{L(G)} = \{t\}$, where $t$ is the transcript of the halting computation of $M$, and if $M$ doesn't halt then $\overline{L(G)} = \emptyset$. Consequently, given a context-free grammar $G$, determining whether $L(G) = \...
2
The language generated by a grammar with no useless symbols/productions is finite if and only if there is no non-terminal $A$ so that $A \Rightarrow^* \alpha A \beta$. This is easy to check.
2
The grammar is, as you say, unambiguous. But it is not deterministic. LR parsers with bounded lookahead can only recognise deterministic languages; since not all unambiguous context-free languages are deterministic, LR parsers cannot recognise all unambiguous context-free languages.
Intuitively, palindromes are non-deterministic because the parser must ...
2
You said:
Here is the grammar given on the wikipedia:
[...]
$T \rightarrow VaT \;|\; VaV \;|\; TaV$
[...]
My doubt is what is the need for the rule $T \rightarrow TaV$
Wikipedia said:
Omitting the third alternative in the rules for T and U doesn't restrict the grammar's language.
2
The reason that $L_1$ is context-free is that one needs to keep track of only two numbers at the same time: either $l=m$ or $m=n$. The 'or' is handled using union, we patch two languages together.
The difference of the two numbers $l-m$ or $m-n$ can be stored on the stack while reading the string.
Your language $L=\{a^mb^nc^n \mid m\neq n\}$ is not context-...
1
One of the possibilities is to keep the topmost $i$ symbols of the stack in the finite memory rather than putting it on the stack.
Any simple symbol replacement of the topmost symbols can be performed in memory, rather than on the stack. If we push or pop symbols from/to the stack we also push or pop from the (shorthened) stack, shifting symbols from/to the ...
1
You can recognize $\{a^nb^n\}$ with just a counter (which is incremented by an $a$ and decremented by a $b$). No additional stack is needed. (If you used a stack, it would only contain $a$s; in general a counter is functionally equivalent to a stack whose alphabet consists of only one symbol.)
The answer to the question you link to provides an example of a ...
1
Your question unfortunately doesn't have a simple answer. The best I can do is go over the proofs and point out where they fail when trying to apply them to the other class.
Regularity of the language generated by a CFG
The proof that regularity of the language generated by a CFG is undecidable is very similar to the proof that universality of the language ...
1
Structurally the classes CFL and DCFL have very different closure properties.
CFL are closed under union, but not under complement.
DCFL are not closed under union, but closed under complement.
The undecidability of regularity for CFL is usually obtained from two properties of the context-free languages: (1) they are closed under union, and (2) universality, ...
1
The set $\Sigma^*$ consists of all words over $\Sigma$.
A language over $\Sigma$ is not a word over $\Sigma$. Hence no language is a member of $\Sigma^*$, and no set of languages is a subset of $\Sigma^*$.
Only top voted, non community-wiki answers of a minimum length are eligible