Comprehensive questions and detailed answers for Unit II: Introduction to Finite Automata (8 Hrs.). Perfect for exam preparation and concept clarity.
Define the NFA with ε-transition and ε-closure of a state. Show that for every regular expression r, representing a language L, there is ε-NFA accepting the same language. Also convert regular expression (a+b)ab into equivalent Finite Automata.
Give the formal definition of DFA. Construct a DFA accepting all strings of {0, 1} with even number of 0’s and even number of 1’s.
Construct a NFA accepting language of {0, 1} with each string ending with 01 and convert it into equivalent DFA.
Give the formal definition of DFA and NFA. How NFA can be converted into eqivalent DFA? Explain with suitable example.
Find the minimum state DFA for the given DFA below:
| States | Input | |
|---|---|---|
| 0 | 1 | |
| A | B | F |
| B | E | C |
| C | B | D |
| *D | E | F |
| E | B | C |
| F | B | A |
Show that, For any NFA N=(Q, ∑, δ, q0, F) accepting language L=∑, There is a DFA D= (Q’, ∑’, q0′, δ’, F’) accepting the same language L.
State and prove the Pumping Lemma for regular languages. How can you show with example that pumping lemma is used to prove that a given language is not a regular? Explain.
Explain the ε-closure of states on an ε-NFA with suitable examples.
What is NFA? How is it different from DFA? How is NFA to DFA conversion done? Convert the following NFA into DFA.
Design a DFA that accepts single line and multi-line comments of the C-Language.
Describe the extended transition function of NFA. Construct a NFA, using transition table and transition diagram , over {0, 1} that accept the string having substring 01 and ends with 1. Show the acceptance of 0111.
Design a Melay machine over {a, b} that generates output ‘A’ if the input string ends with aa else output ‘B’ if the string ends with bb.
List any two regular operators. Minimize the following finite state machine using Table Filling algorithm.
Define ε-closure of a state. Differentiate between Moore and Mealy machine.
Represent the following regular grammar to finite automata. S → aA | aB | ε A → aA | aS B → bB | ε
Design the DFA that accepts binary string ending with “00” and show its extended transition function for the string 111000.
And more questions available on this page.