210 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
asked | 210 views

The given grammar generates balanced parenthesis.

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

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

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

SO,  the answer will be Option D

Correct me if am wrong

answered by Active (1.7k points)
selected

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