The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

- $L(G)$ is context free
- $L(G)$ is infinite
- $L(G)$ can be recognized by a deterministic push down automaton
- $L(G)$ is prefix-closed
- $L(G)$ is recursive

+10 votes

Best answer

*Your answer (d) is correct.*

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 284
- Exam Queries 397
- Tier 1 Placement Questions 17
- Job Queries 51
- Projects 7

33,707 questions

40,253 answers

114,361 comments

38,874 users