MHB Designing NFA & DFA for (1001 + 110 + 11)* Language

AI Thread Summary
The discussion revolves around designing a Non-deterministic Finite Automaton (NFA) for the language defined by the regular expression (1001 + 110 + 11)* and converting it into a Deterministic Finite Automaton (DFA). The original attempt mistakenly included strings not part of the language, prompting feedback on the NFA's structure. Key points include the role of epsilon transitions, which allow movement between states without consuming input, and the necessity for a total transition function in a DFA. Participants clarify that all states in a DFA must have defined transitions for every input symbol, and the discussion highlights the importance of incorporating a sink state for missing transitions. The conversation emphasizes understanding the mechanics of NFAs and DFAs, particularly regarding state transitions and the implications of the Kleene star in language acceptance.
Lolligirl
Messages
22
Reaction score
0
Hello everyone! I'm trying to design an NFA and then turn it into a DFA, and I'm not sure if I've done it correctly so far. Here is the question:

"Present a transition diagram for an NFA for the language associated with the regular expression (1001 + 110 + 11)*. Your NFA must have no more than five states. Then, use the standard conversion technique (subsets of states) to convert the NFA to an equivalent DFA. Be sure to not include unreachable states. Hint: This DFA should have no more than six states."

And here is my attempt at an answer:

View attachment 3147

Would this work as the NFA or DFA? I feel like I'm missing something here, but I am not sure what. Any help is appreciated! :D
 

Attachments

  • Assignment3PossibleNFA.jpg
    Assignment3PossibleNFA.jpg
    11.8 KB · Views: 167
Technology news on Phys.org
Hi, and welcome to the forum!

Your automaton accepts 111 and 10, which are not in the original language. How about the following NFA?

View attachment 3151
 

Attachments

  • automaton1.png
    automaton1.png
    2.9 KB · Views: 157
Oh, I see! Thank you so much for pointing that out, Evgeny: I indeed included the string 10!

Okay, so now I understand the NFA, but I guess I really don't understand what's going on with the epsilon there. Why, from state 5 in the diagram, are we going back to state 1 on epsilon? Also, is that the only thing making this an NFA and not a DFA? As far as I can tell, state 2, for instance, indeed can branch two different ways, but there's only one character per arrow. So I guess my question is basically, what makes this not a DFA already besides the epsilon?

Sorry if this is dead simple! >.<
 
Just to avoid confusion: $\varepsilon$ denotes the empty word, which is also sometimes denoted by $\lambda$. Going from an accepting state back to the initial one on $\varepsilon$ is a usual thing in an automaton accepting $L^*$ for some $L$. This is how we show that the set of languages accepted by NFAs is closed under the Kleene star. In this case, both 11 and 110 should lead to the initial state, which is the reason for the two arrows from 5 to 1.

Yes, $\varepsilon$ makes it an NFA, but also not all states have outgoing arrows for both 0 and 1. In a DFA, the transition function has to be total, i.e., defined on all pairs from $Q\times\Sigma$. If it were not for the $\varepsilon$ arrow, to turn this automaton into a DFA one needs to add a sink state with all the missing arrows going there. By the way, I did not draw a 1-arrow from 2 to 1 because then it's not clear what to do with the word 110 since 0 should be accepted only after two 1's.
 
Ohh! By a sink state, do you mean like a dead state? So would it be kind of like this (D for dead)?

https://dl.dropboxusercontent.com/u/5778771/Assignment3Number1.jpg

Either way, thank you so much, Evgeny; I really feel like I'm starting to get it! :D
 
Let's make that:

View attachment 3161

Since $11$ should be accepted.
And since after $11$ we can get something that starts with a $1$.
 

Attachments

  • deterministic_finitestate_automaton.png
    deterministic_finitestate_automaton.png
    6.7 KB · Views: 129
Right, right, of course! That makes much more sense now; thank you very much for helping me understand, Evgeny, en hartelijk bedankt, I like Serena! :D
 
Last edited:

Similar threads

Replies
3
Views
2K
Replies
4
Views
2K
Replies
1
Views
2K
2
Replies
52
Views
7K
Back
Top