retagged by
545 views
3 votes
3 votes
I read some where that if thier is  one comparision at any time then only CFL otherwise CSL?
plz give proof.
retagged by

1 Answer

Best answer
8 votes
8 votes

That is utter, absolute bullshit. The number of comparisons is ambiguous and ill-defined, so you should avoid using it to determine where a language lies in the Chomsky hierarchy. If one could distinguish between CFL and CSL just based on the number of comparisons, Bar-Hillel wouldn't have invented the Pumping Lemma for CFLs.

How many comparisons do you need to make in $\Bigl \{a^p \mid p \in \text{Primes} \Bigr \}$ ? No comparisons, still CSL.


How about this?

$$\left \{
\begin{array}{l}
\delta & a^w & b^x & \beta & \gamma & c^y  & d^z & \rho
&\left |
\begin{array}{c}
w \cong 0 \pmod{4} \\[0.5em]
x \geq 10, \quad y > z \\[0.5em]
\beta = \gamma^R\\[0.5em]
\delta \in \text{Palindromes}
\end{array}
\right .
\end{array}
\right \}$$

So many comparisons, but still CFL.


And the following is regular:

$$\left \{
\begin{array}{l}
\alpha & \beta & \gamma & \delta
&\left |
\begin{array}{c}
\alpha \in \text{Palindromes} \\[0.5em]
\text{binary}(\gamma) \in \text{Primes} \text{ OR } \gamma = \epsilon \\[0.5em]
\delta \in \Large\substack{\rm Kolmogorov\\\rm complexity\\[0.1em] \rm of\\[0.1em] \rm this~answer}\\[0.5em]
\beta \in \Sigma^*
\end{array}
\right .
\end{array}
\right \}$$

selected by

Related questions

0 votes
0 votes
0 answers
4
iarnav asked Sep 22, 2017
1,334 views
State T/Fif a language is deterministic context free it can always be accepted by a PDA?