The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+9 votes
290 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 in Theory of Computation by Veteran (98.5k points) | 290 views

1 Answer

+12 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.

Correct me if am wrong.

answered by Active (2.1k points)
edited ago by
+2

@sarveswara rao v @Prajwal Bhat 

Prefixes of [ [ ] ] are 

{ epsilon, [, [ [, [ [ ], [ [ ] ] } and only [ [ ] ] belongs to L(G) and not all.

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

Your answer (d) is correct.

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

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

36,075 questions
43,521 answers
123,664 comments
42,747 users