GATE CSE 1998 | Push Down Automata and Context Free Language Question 45 | Theory of Computation

GATE CSE 1998

MCQ (Single Correct Answer)

-0.6

Let $$L$$ be the set of all binary strings whose last two symbols are the same. The number of states in the minimum state deterministic finite-state automation accepting $$L$$ is

$$2$$

$$5$$

$$8$$

$$3$$

GATE CSE 1998

MCQ (Single Correct Answer)

-0.6

Which of the following statements is false?

Every finite subset of a non-regular set is regular

Every subset of a regular set is regular

Every finite subset of a regular set is regular

The intersection of two regular sets is regular

GATE CSE 1997

MCQ (Single Correct Answer)

-0.6

Which of the following languages over $$\left\{ {a,b,c} \right\}$$ is accepted by Deterministic push down automata?

$$\left\{ {w \subset {w^R}\left| {w \in \left\{ {a,b} \right\}{}^ * } \right.} \right\}$$

$$\left\{ {w{w^R}\left| {w \in \left\{ {a,b,c} \right\}{}^ * } \right.} \right\}$$

$$\left\{ {{a^n}{b^n}{c^n}\left| {n \ge 0} \right.} \right\}$$

$$\left\{ {w\left| w \right.} \right.$$ is palindrome over $$\left. {\left\{ {a,b,c} \right\}} \right\}$$

GATE CSE 1996

Subjective

-0

Let $$G$$ be a context free grammar where $$G = \left( {\left\{ {S,A,.B,C} \right\},\left\{ {a,b,d} \right\},P,S} \right)$$ with productions $$P$$ given below
$$\eqalign{ & S \to ABAC\,\,\,\,\,\,\,\,\,S \to aA{\mkern 1mu} \left| \varepsilon \right. \cr & S \to bB{\mkern 1mu} \left| \varepsilon \right.\,\,\,\,\,\,\,\,\,\,\,\,\,\,C \to d \cr} $$

($$\varepsilon $$ denotes the null string). Transform the given grammar $$G$$ to an equivalent context- free grammar $${G^1}$$ that has no $$\varepsilon $$ productions ($$A$$ unit production is of the from $$x \to y,\,x$$ and $$y$$ are non terminals).

PREVIOUS NEXT