New answers tagged

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.
oleshkowitz's user avatar
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 ...
Hendrik Jan's user avatar
  • 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.'s user avatar
  • 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.
Yves Daoust's user avatar
  • 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 ...
reinierpost's user avatar
  • 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.'s user avatar
  • 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 ...
bebidek's user avatar
  • 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 ...
Ṃųỻịgǻňạcểơửṩ's user avatar
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
  • 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. ...
Dartypier's user avatar

Top 50 recent answers are included