Course Content

Other Courses

Tribhuvan university > CSIT - 2065 Syllabus > Compiler Design and Construction > Old Questions > 2071-I

Compiler Design and Construction - Old Questions

Syllabus Notes Old Questions Unit Wise Questions Question Bank

4.  Define finite automata. Construct a finite automata that will accept a string at zeros and ones that contains an odd number of zeros and an even number of ones.

6 marks | Asked in 2071-I

A finite automaton is a mathematical (model) abstract machine that has a set of "state" and its "control" moves from state to state in response to external "inputs". The control may be either "deterministic" meaning that the automation can‘t be in more than one state at any one time, or "non-deterministic", meaning that it may be in several states at once. This distinguishes the class of automata as DFA or NFA.

  • The DFA, i.e. Deterministic Finite Automata can‘t be in more than one state at any time.
  • The NFA, i.e. Non-Deterministic Finite Automata can be in more than one state at a time.

Now,

DFA that will accept a string at zeros and ones that contains an odd number of zeros and an even number of ones is shown below:

Here,

Q = {q0, q1, q2, q3}

∑ = {0, 1}

δ = Above transition diagram

q0 = q0

F = {q2}