Formal language & automata theory

The language $ \{a^m b^n c^{m+n} / m, n \ge 1\} $ is

Which of the following pairs have DIFFERENT expressive powers?

The logic of pumping lemma is a good example of

If $ L_1 $ and $ L_2 $ are context free languages, $ L_1 - L_2 $ is

_____ is the acyclic graphical representation of a grammer.

Which of the following pairs of regular expressions are equivalent?

The maximum number of states of a DFA converted from an NFA with $ n $ states is

Definition of a language L with alphabet {a} is given as $ L = \{a^{nk} / k > 0 \}, $ and n is a positive integer constant. What is the minimum number of states needed in a DFA to recognize L?

A _____ is context free grammar with atmost one non-terminal in the right handside of the production.

Let N be an NFA with $ n $ states and let M be the minimized DFA with $ m $ states recognizing the same language. Which of the following is necessarily true?

Tabulate Chomsky hierarchy of grammars with an example for each.

Construct the regular grammar accepting the following language: $ L = \{w \in \{a,b\}^* / w \text{ is a string over } \{a, b\} \text{ such that the number of b's is } 3 \mod 4\} $

Minimize the DFA.

Define recursively enumerable languages. Let $ L_1 $ be recursive and $ L_2 $ recursively enumerable. Show that $ L_2 - L_1 $ is necessarily recursively enumerable.

Begin with the grammar: $ S \rightarrow ASB/\epsilon $, $ A \rightarrow aAS/a $, $ B \rightarrow 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.

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

Define deterministic pushdown automata. Explain with an example.

Prove using pumping lemma for regular languages that the language $ \{0^n / n \text{ is a perfect square}\} $ is not regular.

Convert the following DFA to regular expression using the state elimination technique.

Convert the following NFA to DFA and informally describe the language it accepts.

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

Define Turing machine. Design a Turing machine M to recognize the language $ \{1^n 2^n 3^n / n \ge 1\} $.

Construct DFA equivalent to the regular expression: $ (0+1)^*(00+11)(0+1)^* $

The language $ \\{a^m b^n c^{m+n} / m, n \ge 1\\} $ is

Which of the following pairs have DIFFERENT expressive powers?

The logic of pumping lemma is a good example of

If $ L_1 $ and $ L_2 $ are context free languages, $ L_1 - L_2 $ is

_____ is the acyclic graphical representation of a grammer.

Which of the following pairs of regular expressions are equivalent?

The maximum number of states of a DFA converted from an NFA with $ n $ states is

Definition of a language L with alphabet {a} is given as $ L = \\{a^{nk} / k > 0 \\}, $ and n is a positive integer constant. What is the minimum number of states needed in a DFA to recognize L?

A _____ is context free grammar with atmost one non-terminal in the right handside of the production.

Let N be an NFA with $ n $ states and let M be the minimized DFA with $ m $ states recognizing the same language. Which of the following is necessarily true?

Tabulate Chomsky hierarchy of grammars with an example for each.

Construct the regular grammar accepting the following language: $ L = \\{w \in \\{a,b\\}^* / w \text{ is a string over } \\{a, b\\} \text{ such that the number of b's is } 3 \mod 4\\} $

Minimize the DFA.

Define recursively enumerable languages. Let $ L_1 $ be recursive and $ L_2 $ recursively enumerable. Show that $ L_2 - L_1 $ is necessarily recursively enumerable.

Begin with the grammar: $ S \rightarrow ASB/\epsilon $, $ A \rightarrow aAS/a $, $ B \rightarrow 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.

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

Define deterministic pushdown automata. Explain with an example.

Prove using pumping lemma for regular languages that the language $ \\{0^n / n \text{ is a perfect square}\\} $ is not regular.

Convert the following DFA to regular expression using the state elimination technique.

Convert the following NFA to DFA and informally describe the language it accepts.

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

Define Turing machine. Design a Turing machine M to recognize the language $ \\{1^n 2^n 3^n / n \ge 1\\} $.

Construct DFA equivalent to the regular expression: $ (0+1)^*(00+11)(0+1)^* $