# Tag Info

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 ...

### 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 ...

### 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.

### 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 ...
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 ...

### 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 ...

### 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 ...
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 ...
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. ...