2,808 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

2 Answers

Best answer
25 votes
25 votes

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
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
Answer:

Related questions

12 votes
12 votes
6 answers
2
go_editor asked Dec 23, 2016
2,245 views
Which of the following regular expressions correctly accepts the set of all $0/1$-strings with an even (possibly zero) number of $1$s?$(10^*10^*)^*$$(0^*10^*1)^*$$0^*1(10...