508 views
2 votes
2 votes

I am having problem while converting it into NFA since it is an epsilon-NFA , so I got 

q0----> {q0,q1,q2} on a 

q1---> {q0,q1,q2} on a 

then finally for DFA I got {q0,q1,q2} and q0 as two states such that {q0,q1,q2}---> {q0,q1,q2} on a and q0 --->{q0,q1,q2} on a ,plz tell the mistake ,I am unable to catch it.

http://gatecse.in/w/images/c/c5/2012_12.png

2 Answers

Best answer
3 votes
3 votes

I. Check the strings reaching the final state 

 { a,aa,aaa,aaaa,......} = a+ , or, { all strings over {a}, except ∊}

II. Remove ∊-moves 

∊-closure(q0) = {q0}

∊-closure(q1) = {q0,q1,q2}

∊-closure(q2) = {q0,q2}

NFA with ∊-moves to NFA 

States\Symbols a
->q0 {q0,q1,q2}
q1* {q0,q1,q2}
q2 {q0,q1,q2}

DFA 

States\Symbols a
->q0 {q0,q1,q2}
{q0,q1,q2}* {q0,q1,q2}

 

L = a =  {a,aa,aaa,aaaa,aaaaa,....}

selected by
0 votes
0 votes
let p0 be the initial state and let p1={q0,q1,q2}

then, p0->p1 on a;

p1-> p1 on a.

This is the DFA I got.

Hence the language is aa*. Is this right?

Related questions

2 votes
2 votes
2 answers
2
set2018 asked Nov 8, 2017
1,176 views
in this b,c,d all are true .how can we find the appropriate one ?
0 votes
0 votes
1 answer
3
$ourav asked May 7, 2016
335 views
S → S0S1S0S | S0S0S1S | S1S0S0S | ϵ
1 votes
1 votes
1 answer
4
GateAspirant999 asked Mar 2, 2018
1,034 views
Language accepted by following NFA and number of states in DFA accepting that Language are:$\{a^n|n=2k,kϵN\}$ and 2$\{a^{2n}|n=2k,kϵN\}$ and 2$\{a^n|n=2k,kϵ N\}$ and 3...