Biju Patnaik University of Technology 2007-5th Sem B.Tech Computer Science and Engineering AUTOMATA THEORY CLASS TEST-1 - Question Paper

AUTOMATA THEORY 5TH SEM CLASS TEST-1 MAX. MARKS-10
ans any 4 ques.. All ques. carry equal marks.

1.Define Deterministic Finite Automata
2.Draw the state diagram of the 2 state finite automaton M where the state transition table is
0 1
q1 q1 q2
q2 q1 q2
3.Draw the state diagram of DFA recognizing the subsequent language:
{w|w starts with a one and ends with a 0}
4.Give a NFA recognizing the language
{w|w contain the substring 0101 i.e. w=x0101y for a few x and y}
5.What is the expression describing the language
{w|w is of even length constructed from alphabet ?={a,b}}

Earning:   Approval pending.