GATE CS Context-free Grammars and Push-down Automata questions

Consider the following grammar where

S

is the start symbol, and

a

and

b

are terminal symbols.

S \rightarrow a S b S \text{ | } b S \text{ | } \epsilon

Which of the following statements is/are true?

Consider the following context-free grammar

G

, where

S, A

, and

B

are the variables (non-terminals),

a

and

b

are the terminal symbols,

S

is the start variable, and the rules of

G

are described as:

\begin{array}{l} S \rightarrow a a B \mid A b b \\ A \rightarrow a \mid a A \\ B \rightarrow b \mid b B \end{array}

Which ONE of the …

Which ONE of the following languages is accepted by a deteministic pushdown automaton?

Consider the context-free grammar

G

below

\begin{array}{l} S \rightarrow a S b \mid X \\ X \rightarrow a X \mid X b \mid a \mid b, \end{array}

where

S

and

X

are non-terminals, and

a

and

b

are terminal symbols. The starting non-terminal is

S

. Which one of the following statements is

\text{CORRECT}?

Consider the pushdown automaton

\text{(PDA)}\;P

below, which runs on the input alphabet

\{a, b\}

, has stack alphabet

\{\perp, A\}

, and has three states

\{s, p, q\}

, with

s

being the start state. A transition from state

u

to state

v

, labelled

c / X / \gamma

, where

c

is an input symbol or

\epsilon, X

is a stack symbol, …

Consider the following languages:

L_{1} = \{ ww | w \in \{a,b\}^{\ast} \}

L_{2} = \{a^{n} b^{n} c^{m} | m,n \geq 0 \}

L_{3} = \{a^{m} b^{n} c^{n} | m,n \geq 0 \}

Which of the following statements is/are

\text{FALSE}?

Consider the following languages:

L_{1} = \{ a^{n} wa^{n} | w \in \{a,b\}^{\ast}\}

L_{2} = \{wxw^{R} | w, x \in \{a,b\}^{*}, |w|, |x| > 0 \}

Note that

w^{R}

is the reversal of the string

w.

Which of the following is/are

\text{TRUE}?

Suppose that

L_1

is a regular language and

L_2

is a context-free language. Which one of the following languages is

\text{NOT}

necessarily context-free?

In a pushdown automaton

P=(Q, \Sigma, \Gamma, \delta, q_0, F)

, a transition of the form, where

p,q \in Q

,

a \in \Sigma \cup \{ \epsilon \}

, and

X,Y \in \Gamma \cup \{ \epsilon \}

, represents

(q,Y) \in \delta(p,a,X).

Consider the following pushdown automaton over the input alphabet

\Sigma = \{a,b\}

and stack alphabet …

For a string

w

, we define

w^R

to be the reverse of

w

. For example, if

w=01101

then

w^R=10110

. Which of the following languages is/are context-free?

Which one of the following languages over

\Sigma=\{a, b\}

is NOT context-free?

Consider the following languages:

\{a^mb^nc^pd^q \mid m+p=n+q, \text{ where } m, n, p, q \geq 0 \}

\{a^mb^nc^pd^q \mid m=n \text{ and }p=q, \text{ where } m, n, p, q \geq 0 \}

\{a^mb^nc^pd^q \mid m=n =p \text{ and } p \neq q, \text{ where } m, n, p, q \geq 0 \}

\{a^mb^nc^pd^q \mid mn =p+q, \text{ where } m, n, p, q \geq 0 \}

Which of the …

Consider the following languages over the alphabet

\Sigma = \left \{ a, b, c \right \}

. Let

L_{1} = \left \{ a^{n}b^{n}c^{m}\mid m,n \geq 0 \right \}

and

L_{2} = \left \{ a^{m}b^{n}c^{n}\mid m,n \geq 0 \right \}

. Which of the following are context-free languages?

L_{1} \cup L_{2}

L_{1} \cap L_{2}

Consider the context-free grammars over the alphabet

\left \{ a, b, c \right \}

given below.

S

and

T

are non-terminals.

G_{1}:S\rightarrow aSb \mid T, T \rightarrow cT \mid \epsilon

G_{2}:S\rightarrow bSa \mid T, T \rightarrow cT \mid \epsilon

The language

L\left ( G_{1} \right )\cap L(G_{2})

is

If

G

is a grammar with productions

S\rightarrow SaS\mid aSb\mid bSa\mid SS\mid\epsilon

where

S

is the start variable, then which one of the following strings is not generated by

G

?

Consider the following context-free grammar over the alphabet

\Sigma = \{a,b,c\}

with

S

as the start symbol:

S \rightarrow abScT \mid abcT

T \rightarrow bT \mid b

Which one of the following represents the language generated by the above grammar?

Identify the language generated by the following grammar, where

S

is the start variable.

S \rightarrow XY

X \rightarrow aX \mid a

Y \rightarrow aYb \mid \epsilon

Consider the transition diagram of a PDA given below with input alphabet

\Sigma=\{a,b\}

and stack alphabet

\Gamma = \{X,Z\}

.

Z

is the initial stack symbol. Let

L

denote the language accepted by the PDA Which one of the following is TRUE?

Consider the following context-free grammars;

G_1 : S \to aS \mid B, B \to b \mid bB

G_2 : S \to aA \mid bB, A \to aA \mid B \mid \varepsilon,B \to bB \mid \varepsilon

Which one of the following pairs of languages is generated by

G_1

and

G_2

,respectively?

Which of the following languages is generated by the given grammar?

S \rightarrow aS \mid bS \mid \varepsilon