0
$\begingroup$

Consider the language of all words over {a, b} that either begins and ends with aa or bb (but both are the same within each word). That is, {ccycc | c ∈ {a, b}, y ∈ Σ ∗}

enter image description here

I have drawn the resulting NFA for the language described above, what would the corresponding DFA look like? What would the steps look like to get from an NFA to a DFA?

$\endgroup$

2 Answers 2

Reset to default
0
$\begingroup$

In this case you are very close to a DFA already. First add a 'dead state' (non-final) with additional transitions to it from q1, q2, q5, and q6 on symbols b, a, b, and a, respectively, plus an arrow from the state to itself on a and b. Second, split q7 into two final states q8, q9, with q5->q8 on a and q6->q9 on b, and add loops q8->q8 on a, q9->q9 on b, and cross-transitions q8->q6 on b, q9->q5 on a.

$\endgroup$
2
  • $\begingroup$ That doesn’t quite work: you end up accepting $aaaabb$, which is not in the language. $\endgroup$
    – Brian M. Scott
    Feb 12, 2021 at 17:50
  • $\begingroup$ @BrianM.Scott Would the DFA I recently posted work? $\endgroup$
    – M. Petras
    Feb 12, 2021 at 18:25
0
$\begingroup$

enter image description here

I believe this DFA would work.

$\endgroup$
2
  • 1
    $\begingroup$ Almost, but you need the $b$ transition from $q_8$ to go to $q_4$, and the $a$ transition from $q_7$ to go to $q_3$. As it stands, it accepts $aabaaba$, which it should not do. $\endgroup$
    – Brian M. Scott
    Feb 12, 2021 at 18:28
  • $\begingroup$ Thank you very much for the help! @BrianM.Scott $\endgroup$
    – M. Petras
    Feb 12, 2021 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.