• Attempt any five questions.
• All questions carry equal marks.
Convert the following Mealy machine into equivalent Moore machine.
Draw the DFA for the following language over {0,1} such that all the strings with even number of 0's and even number of 1's.
Design Finite Automata which checks whether a given binary number is divisible by three.
Explain different types of automata machines in detail.
How does Two-Way DFA differ from ordinary DFA?
Construct DFA equivalent to given NFA.
| State\Input | 0 | 1 |
|---|---|---|
| →p | p | |
| q | r | r |
| r | s | — |
| s | s | s |
Construct an -NDFA for the regular expression .
State and prove Arden's Theorem.
Explain different types of grammars with suitable examples.
Define Chomsky normal form and Greibach normal form in reference to context free languages. Give suitable example.
Explain a parse tree in detail.
Describe null () production in detail.
Define concept and working of Push Down Automata (PDA).
Explain the difference between deterministic and non-deterministic pushdown automata, giving their definition. Also give example of each.
Explain the Halting problem in detail.
Explain how a Turing machine can be viewed as a computing device on functions involving integers.
