New answers tagged formal-languages
1
vote
Accepted
Is $L=\{1^n2^n3^m : n\neq m\}$ context free?
The language is not context free, and indeed Ogden's Lemma can be used to show so. See the answer in the following duplicate.
- 76
1
vote
Accepted
How to prove L := { a^n b^n c^m | n,m >= 0 & n != m } is not context-free?
Your analysis is correct. In order to keep the $a^n b^n c^m$ structure of the string, the only ways to pump are case (2) pump both $a$'s and $b$'s, or case (5) pump only $c$'s. All other case will ...
- 29.6k
0
votes
Why do we use CYK algorithm?
As Wikipedia states:
The importance of the CYK algorithm stems from its high efficiency in certain situations.
In particular, its relevance is that it allows parsing an arbitrary context-free ...
D.W.♦
- 154k
2
votes
Can you verify the end of a function declaration through syntax analysis?
Nope,
PROCEDURE P;
BEGIN
END Q;
is syntactically valid. A BNF description cannot express the equality of the identifiers.
- 10.3k
2
votes
Can you verify the end of a function declaration through syntax analysis?
It depends on what is meant by a syntax analyzer.
Generally, in computer science, different people often mean different things by the same term, so always consult the definition you were given.
It is ...
- 5,349
10
votes
Accepted
Is the language given by the regex (ab)* star-free?
No. $L=(ab)^*$ is star-free. A word is in $L$ iff
It starts with $a$ (or is empty)
It ends with $b$ (or is empty)
It does not contain any consecutive $a$'s
It does not contain any consecutive $b$'s
...
D.W.♦
- 154k
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 ...
- 161
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 ...
- 280
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 ...
- 616
0
votes
How to prove {a^(n^2) | n>0} is not context-free?
Assume that the language $L = \{a^{(n^2)} | n > 0\}$ is context-free and let N be the pumping length given by the Pumping Lemma.
Choose the string $u = a^{(N^2)}$, which is in the language L. ...
Top 50 recent answers are included