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

1 Answer

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

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

29,966 questions
37,651 answers
35,292 users