261 views

Consider the following grammar $G$ with terminals  $\{[, ]\}$, start symbol $S$, and non-terminals $\{A, B, C\}$:

$$S \rightarrow AC \mid SS \mid AB$$

$$C \rightarrow SB$$

$$A \rightarrow [$$

$$B \rightarrow ]$$

A language $L$ is called prefix-closed if for every $x \in L$, every prefix of $x$ is also in $L$. Which of the following is FALSE?

1. $L(G)$ is context free
2. $L(G)$ is infinite
3. $L(G)$ can be recognized by a deterministic push down automaton
4. $L(G)$ is prefix-closed
5. $L(G)$ is recursive

The given grammar generates balanced parenthesis.

Lets take a smallest string : $[ \ [ \ ] \ ]$   (say $x$ )

Prefixes of $x$ are : $[ , [ \ [ ,[ \ [ \ ]$

BUT they don't belong to the language generated by the given grammar.

SO,  the answer will be Option D

Correct me if am wrong

edited ago by

for n length we have (n+1) prefix.

Note: The given language is prefix-free due to the above reason and hence not prefix-closed.
can anyone tell me wats wrong with option A and C ??