Instructions:
- The marks are indicated in the right-hand margin.
- There are NINE questions in this paper.
- Attempt FIVE questions in all.
- Question No. 1 is compulsory.
Q.1 Choose the correct option of the following (Any seven question
only):
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?
Q.2 Solve both questions :
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\} $
Q.3 Solve both questions :
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.
Q.4 Solve this question :
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.
Q.5 Solve both questions :
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.
Q.6 Solve both questions :
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.
| State / input | 0 | 1 |
|---|---|---|
| → *p | s | p |
| q | p | s |
| r | r | q |
| s | q | r |
Q.7 Solve both questions :
Convert the following NFA to DFA and informally describe the language it accepts.
| State / input | 0 | 1 |
|---|---|---|
| p | {p, q} | {p} |
| q | {r, s} | {t} |
| r | {p, r} | {t} |
| s | ∅ | ∅ |
| *t | ∅ | ∅ |
When a CFG is called ambiguous? Show that $ S \rightarrow aS / aSbS / \epsilon $ is ambiguous.
Q.8 Solve both questions :
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)^* $
Q.9 Write short notes on any two of the following:
Instructions:
- The marks are indicated in the right-hand margin.
- There are NINE questions in this paper.
- Attempt FIVE questions in all.
- Question No. 1 is compulsory.
Q.1 Choose the correct option of the following (Any seven question
only):
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?
Q.2 Solve both questions :
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\\} $
Q.3 Solve both questions :
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.
Q.4 Solve this question :
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.
Q.5 Solve both questions :
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.
Q.6 Solve both questions :
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.
| State / input | 0 | 1 |
|---|---|---|
| → *p | s | p |
| q | p | s |
| r | r | q |
| s | q | r |
Q.7 Solve both questions :
Convert the following NFA to DFA and informally describe the language it accepts.
| State / input | 0 | 1 |
|---|---|---|
| p | {p, q} | {p} |
| q | {r, s} | {t} |
| r | {p, r} | {t} |
| s | ∅ | ∅ |
| *t | ∅ | ∅ |
When a CFG is called ambiguous? Show that $ S \rightarrow aS / aSbS / \epsilon $ is ambiguous.
Q.8 Solve both questions :
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)^* $