in Theory of Computation
2,789 views
19 votes
19 votes

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
in Theory of Computation
2.8k views

2 Answers

25 votes
25 votes
Best answer

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.

edited by

4 Comments

edited by
No, here Prefix closed means for every string x in L, all its prefixes should also be in the language.

let say x = [ [ ] ] ( x is  in L)

'[' is its prefix but it is not in L, So L isn't prefix closed.

In other way, epsilon is prefix of every string but this grammar doesn't generate epsilon So it can't be prefix closed.

Don't go by the prefix property here, read the definition of prefix closed in the question and solve accordingly.
0
0
I think the above language is not DCFL. Please confirm.
0
0
@roh it is.
0
0
0 votes
0 votes
1st reduce the grammer by replacing the Variables with terminals.

we'll get,

$S\rightarrow [S]/SS/[]$

It's looks like $S\rightarrow SS/aSb/ab$ which is clearly a language of balanced parenthesis.

($a^{n}b^{n}$)($a^{n}b^{n}$) | n is greater or equal to 1

aaaabbbbab

So every prefix is not present. Not prefix closed.

Option D
edited by

3 Comments

@MRINMOY_HALDER

D) option tells prefix closed. But u r concluding not prefix closed.

0
0
Why will it be not context free?
0
0
qsn is saying which of the following is false.
It's a context free language.
1
1
Answer:

Related questions