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

1 Answer

+10 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

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

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 ??


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

33,707 questions
40,253 answers
114,361 comments
38,874 users