The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+10 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 (111k points) | 434 views

1 Answer

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

Since G is context free grammar so L(G) is context free. so A is true
Prefix closed means it doesn't satisfy prefix property??
Prefix property is different, that is used in the context of prefix codes like- huffman codes, Prefix closed here means,

If x is a string in L then every prefix of x will also be in L.

Prefix property means, no two strings in L will have same prefix.

Hope that helps!
whats wrong with option C?

becase above grammar cannot be recognised by D-PDA.

Dushyant Raut 4 why its not recognized by dpda?

Its, S->[ S ] / SS / [ ]

L=(ambmanbn/ m,n >=1}

vishalshrm539  "Prefix property means, no two strings in L will have same prefix." ?  I didn't get this. Plz explain. In my comment I meant prefix property of dpda which states "If a string is a member of the language then no proper prefix of that string should be a member of the language. "

Language of G is asked not the grammar.

Its L(G) not the G


Let say, L = { ab, ac}

It satisfies the prefix property

L' = { ab , abc}

It doesn't.


A prefix code is a type of code system distinguished by its possession of the "prefix property", which requires that there is no whole code word in the system that is a prefix  of any other code word in the system.

Hope it clears the doubt!

that means option c is also right answer

Dushyant Raut 4 question asked which is false, c is true

vishalshrm539 so its correct? "Prefix closed means it doesn't satisfy prefix property"

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.

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

44,161 questions
49,646 answers
65,809 users