Formal Language & Automata Theory

The language $\{ a^m b^n c^{m+n} / m, n \ge 1 \}$ is
(i) regular
(ii) context-free but not regular
(iii) Context-sensitive but not context free
(iv) type-0 but not context sensitive

Which of the following versions of Unix came up with YACC first?

(i) V3
(ii) V5
(iii) CB UNIX
(iv) UNIX-RT

Which of the following pairs have DIFFERENT expressive powers?
(i) Deterministic finite automata (DFA) and non-deterministic finite automata (NDFA)
(ii) Deterministic push-down automata (DPDA) and non-deterministic push-down automata (NDPDA)
(iii) Deterministic single-tape Turing machine and non-deterministic single-tape Turing machine
(iv) Single-tape Turing machine and multi-tape Turing machine

A pushdown automata can be represented as $\text{PDA} = \epsilon\text{-NFA} + [\text{stack}]$.

(i) True
(ii) False

The language $\{a^mb^nc^{m+n} \mid m, n \ge 1\}$ is

(i) regular
(ii) context-free but not regular
(iii) context-sensitive but not context-free
(iv) type-0 but not context-sensitive

Consider the following languages:
GATE[2005]
$$L_1 = \{ww^R \mid w \in \{0, 1\}^*\}$$
$$L_2 = \{w\#w^R \mid w \in \{0, 1\}^*\}$$
where $\#$ is a special symbol,
$$L_3 = \{ww \mid w \in \{0, 1\}^*\}$$

Which one of the following is true?
(i) $L_1$ is a deterministic CFL
(ii) $L_2$ is a deterministic CFL
(iii) $L_3$ is a CFL, but not a deterministic CFL
(iv) $L_3$ is a deterministic CFL

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

If $L1$ and $L2$ are context free languages, $L1 - L2$ is ___________ context-free.
(i) always
(ii) sometimes
(iii) never
(iv) None of these

Consider the following statements about the context-free grammar:
(1) $G = \{S \to SS, S \to ab, S \to ba, S \to \epsilon\}$
(2) $G$ is ambiguous
(3) $G$ produces all strings with equal number of $a$'s and $b$'s

$G$ can be accepted by a deterministic PDA. Which combination below expresses all the true statements about $G$?
(i) 1 only
(ii) 1 and 3
(iii) 2 and 3
(iv) 1, 2 and 3

If L1 and L2 are context-free languages, L1-L2 is ____ context-free.

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

___________ is the acyclic graphical representation of a grammar
(i) Binary tree
(ii) Octtree
(iii) Parse tree
(iv) None of the above

Context-Free Grammars are equivalent to

(i) Finite Automata
(ii) Turing Machines
(iii) Linear Bounded Automata
(iv) Pushdown Automata

Which of the following does not have left recursions?

(i) Chomsky normal form
(ii) Greibach normal form
(iii) Backus-Naur form
(iv) All of the above

Pumping Lemma for CFLs is used to prove a language is

(i) Not Context-Free
(ii) Regular
(iii) Decidable
(iv) Turing recognizable

Consider the grammar $G$ whose SLR parser has $n_1$ states and LALR parser has $n_2$ states. What is the relation between $n_1$ and $n_2$?

(i) $n_1 = n_2$
(ii) $n_1 < n_2$
(iii) $n_1 > n_2$
(iv) None of the above

____ is the acyclic graphical representation of a grammar.

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

A ___________ is context free grammar with atmost one non-terminal in the right handside of the production.
(i) linear grammar
(ii) linear bounded grammar
(iii) regular grammar
(iv) None of the above

Write the context-free grammar to create palindrome over $\{a, b\}$.

Design a push-down automata for accepting the string for the language $L = \{WW^R \mid W \in \{a, b\}^*\}$ by the empty stack as well as final state.

Design ANPDA for accepting the string $L = \{\text{set of all palindrome over } \{a, b\}\}$ by the empty stack and by final state.

Construct a push-down automata that accepts the following language:

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

Begin with the grammar:
$S \to ASB / \epsilon$
$A \to aAS / a$
$B \to SbS / A / bb$

(i) Eliminate $\epsilon$-productions.
(ii) Eliminate unit productions in the resulting grammar.
(iii) Eliminate any useless symbol in the resulting grammar.
(iv) Put the resulting grammar into CNF.

Explain how ambiguity arises in the grammar $E \rightarrow E + E \mid E \times E \mid id \mid (E)$. Remove the ambiguity by rewriting the grammar.

Design a pushdown automata to accept the following language by empty stack: $\{ 0^n 1^n / n \ge 1 \}$.

Consider the grammar:

$$S \to AB \mid BC$$
$$A \to BA \mid a$$
$$B \to CC \mid b$$
$$C \to AB \mid a$$

Use the CYK algorithm to determine whether the given string "baaba" is in $L(G)$ or not.

Prove that the language $L = \{a^{i^2} \mid i \ge 1\}$ is not context-free language.

Show given grammar over alphabet $\{a, b\}$ verify whether it is ambiguous or unambiguous:

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

Suppose $L$ is context free and $R$ is regular, justify your answer with the help of example:

(i) Is $L-R$ necessarily context free?
(ii) Is $R-L$ necessarily context free?

Define deterministic pushdown automata. Explain with an example.

Using Pumping Lemma for CFLs, prove that $L = \{a^{n}b^{n}c^{n} \mid n \ge 0\}$ is not context-free.

Consider the following language:
$$L = \{a^m b^{2n} c^{3n} d^p \mid p > m \text{ and } m, n \ge 1\}$$

Write a context-free grammar to generate $L$ and write shortest string in $L$.

Prove that if $L$ is generated by a CFG, then $L$ is accepted by a non-deterministic PDA by empty stack.

Convert the following context-free grammar into GNF:
$$S \to XY$$
$$X \to YS \mid b$$
$$Y \to SX \mid a$$

Design a pushdown automaton for the following context-free grammar:

$$S \to aB \mid bA$$
$$A \to aS \mid bAA \mid a$$
$$B \to bS \mid aBB \mid b$$

Let $G$ be a context-free grammar in Chomsky normal form that contains $b$ variable. Show that if $G$ generates some string using a derivation with at least $2^b$ steps, then $L(G)$ is infinite.

Construct a push-down automata that accepts the following language:
$$L = \{uawb \mid u \text{ and } w \in \{a, b\}^* \text{ and } |u| = |w|\}$$

Using the following grammar
$$S \to AB \mid BC$$
$$A \to BA \mid a$$
$$B \to CC \mid b$$
$$C \to AB \mid a$$

use the CYK algorithm to determine whether the given string $baaba$ is in $L(G)$ or not.

When a CFG is called ambiguous? Show that $S \to as / aSbS / \epsilon$ is ambiguous.

Show given grammar over alphabet $\{a, b\}$, verify whether it is ambiguous or unambiguous:

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

Design a pushdown automata for accepting the string for the language $L = \{WW^R \mid W \in \{a, b\}^*\}$ by the empty stack as well as final state.

Construct a PDA that accepts the language $L = \{a^{2n}bc \mid n \ge 0\}$ by final state and empty stack.

Write a short note on:

Pushdown Automata

Write a short note on: Type 2 grammar (context free)

Write a short note on: Chomsky normal form

Write a short note on: Pumping lemma for CFL

Write a short note on:

Closure properties of CFLs

Write short notes on: Pumping lemma for CFL

Write short notes on: GNF