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.
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 ...
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.
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 ...
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 ...
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 ...
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 ...
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
Related Tags
formal-languages × 2796regular-languages × 812
context-free × 769
formal-grammars × 565
automata × 437
finite-automata × 321
turing-machines × 270
pumping-lemma × 249
regular-expressions × 218
closure-properties × 204
computability × 164
pushdown-automata × 159
undecidability × 111
complexity-theory × 96
parsers × 85
proof-techniques × 72
context-sensitive × 56
algorithms × 53
terminology × 51
reference-request × 49
compilers × 47
reductions × 42
programming-languages × 41
nondeterminism × 40
semi-decidability × 30