FORMAL LANGUAGE & AUTOMATA THEORY

A language accepted by deterministic pushdown automata is closed under which of the following?

(i) Complement
(ii) Union
(iii) Both (i) and (ii)
(iv) None of the above

Context-free languages are NOT closed under

(i) Union
(ii) Concatenation
(iii) Intersection
(iv) Kleene star

If $L_1$ and $L_2$ are CFLs, $L_1 - L_2$ is ____ context-free.

(i) always
(ii) sometimes
(iii) never
(iv) None of the above

A given grammar is called ambiguous if:

(i) two or more productions have the same non-terminal on LHS
(ii) a derivation tree has more than one associated sentence
(iii) there exists a sentence with more than one derivation tree
(iv) brackets are not present in the grammar

Which of the following does not have left recursion?

(i) Chomsky Normal Form
(ii) Greibach Normal Form
(iii) Backus–Naur Form
(iv) All of the above

Which one of the following statements is true?

(i) The intersection of two CFLs is context-free
(ii) Every CFL can be accepted by a DPDA
(iii) The union of two CFLs is context-free
(iv) The complement of a CFL is context-free

____ is the acyclic graphical representation of a grammar.

(i) Binary tree
(ii) Octtree
(iii) Parse tree
(iv) None of the above

Which of the following CFLs is deterministic?

(i) {$a^n b^n$}
(ii) Arithmetic expressions
(iii) Palindromes
(iv) {$ww^R$}

Which of the following is a PDA?

(i) Finite automaton with a stack
(ii) Turing machine with a stack
(iii) Finite automaton with a queue
(iv) Turing machine with a queue

Given the grammar
$G = (\{S\}, \{a, b\}, P, S)$
$P: S \rightarrow aSb | ab$

Derive the string aabb using leftmost derivation, rightmost derivation and also draw the parse tree.

State the pumping lemma for context-free languages.

Prove that if $L$ is accepted by a PDA, then $L$ can be generated by a CFG.

Design a context-free grammar (CFG) that generates all palindromes over the alphabet {0, 1}. The grammar should generate both even-length palindromes (e.g., 0110) and odd-length palindromes (e.g., 010).

Design a PDA (empty stack and final state both) for $L = \{ WW^r \mid W \in \{a,b\}^* \}$.

Eliminate $\varepsilon$, unit, and useless productions from the grammar:

A → bA | Bba | aa
B → aba | b | D
C → CA | AC | B
D → a | $\varepsilon$

Design an NPDA (empty stack and final state acceptance) for:

$$L = \{\text{palindromes over } \{a,b\}\}$$

Construct a PDA that accepts:

$$L = \{ u a w b : u,w \in \{a,b\}^*,\; |u| = |w| \}$$

Define Chomsky Normal Form. Convert the CFG:

S → aSb | ab | Aa
A → aab

to CNF.

Show whether the given grammar is ambiguous:

$$S \to a \mid abSb \mid aAb \\ A \to bS \mid aAAb$$

Using the CYK algorithm, determine whether baaba is in $L(G)$ for the grammar:

S → AB | BC
A → BA | a
B → CC | b
C → AB | a

Show that the following grammar is ambiguous:
$S \rightarrow SS | aSb | bSa | \epsilon$

Write the difference between Pushdown Automata and Finite Automata.

Suppose $L$ is CFL and $R$ is regular:

(i) Is $L - R$ always CFL?
(ii) Is $R - L$ always CFL?

Construct a PDA for the language:

$$L = \{ 0^m 1^n 0^k \mid k \ge 1, m \ge 1, m > n + 2 \}$$

Construct a CFG for:

$$\{ 0^i 1^j 2^k \mid i + j \ge 2k \}$$

Convert the CFG to GNF:

$$S \to AB \mid BC \\ A \to aB \mid bA \mid a \\ B \to bB \mid cC \mid b \\ C \to c$$

Let $G$ be a CFG in CNF with $b$ variables. Show that if $G$ derives any string using at least $2^b$ steps, then $L(G)$ is infinite.

Construct a PDA for the grammar:

$S \to 0BB$
$B \to 0S \mid 1S \mid 0$

Test whether $0104$ is accepted by this PDA.

Construct NPDA for the grammar:

$$S \to \alpha ABB \mid \alpha AA \\ A \to \alpha BB \mid \alpha \\ B \to bBB \mid A$$

Check whether the grammar is ambiguous:

$S \to a \mid abSb \mid aAb$
$A \to bS \mid aAAb$

Check whether the grammar:

$$S \to aSa \mid bSb \mid a \mid b$$

is ambiguous.

Construct FOLLOW sets for the grammar:

$$E \to T E' \\ E' \to +\,T\,E' \mid \varepsilon \\ T \to F T' \\ T' \to -\,F\,T' \mid \varepsilon \\ F \to (E) \mid id$$

Given the grammar:

$$S \to aB \mid ba \\ B \to b \mid bs \mid aBB$$

For the string $aaabbabbba$ find:

1. Leftmost derivation
2. Rightmost derivation
3. Parse tree

Given the regular expression $r = (a+b)^*$

(i) Construct a context-free grammar that generates the language described by $r$.
(ii) Explain why the grammar correctly represents the given regular expression.

Construct a PDA accepting:

$$L = \{ a^{2n}bc : n \ge 0 \}$$

Write a short note on Chomsky Normal Form.

Write a short note on Deterministic vs Nondeterministic PDA.

Write a short note on Deterministic PDA vs. Non-deterministic PDA.

Write a short note on Chomsky Normal Form (CNF).

Write short notes on: Pumping lemma for CFL.

Write a short note on the Pumping Lemma for CFL.

Write a short note on Greibach Normal Form (GNF).