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

In summary, Evgeny pointed out that the NFA has a transition from state 5 to 1 on the epsilon symbol, which is not the same as a DFA that would have a transition from 2 to 1. The automaton needs a sink state, which is why it doesn't have one.
  • #1
Lolligirl
23
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: 97
Technology news on Phys.org
  • #2
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: 94
  • #3
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! >.<
 
  • #4
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.
 
  • #5
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
 
  • #6
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: 67
  • #7
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:

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

1. What is the difference between NFA and DFA for this language?

NFA stands for Non-Deterministic Finite Automaton, while DFA stands for Deterministic Finite Automaton. The main difference between the two is that NFAs can have multiple possible states for a given input, while DFAs have only one unique state for each input. In terms of designing an NFA and DFA for the (1001 + 110 + 11)* language, the NFA would have more states and transitions compared to the DFA.

2. How do you design an NFA for this language?

To design an NFA for the (1001 + 110 + 11)* language, you first need to determine all possible combinations of 1001, 110, and 11. These combinations will serve as the states of the NFA. Then, you need to create transitions between these states based on the input symbols 0 and 1. The final state of the NFA would be an accepting state, indicating that the input string belongs to the language.

3. Can you provide an example of an NFA for this language?

Yes, here is an example of an NFA for the (1001 + 110 + 11)* language:

NFA for (1001 + 110 + 11)* language

4. How do you design a DFA for this language?

To design a DFA for the (1001 + 110 + 11)* language, you need to first determine the states and transitions based on the input symbols 0 and 1, similar to an NFA. However, in a DFA, you need to ensure that there is only one unique state for each input symbol. Additionally, you will need to include dead states to reject inputs that do not belong to the language. The final state of the DFA would be an accepting state, indicating that the input string belongs to the language.

5. Can you provide an example of a DFA for this language?

Yes, here is an example of a DFA for the (1001 + 110 + 11)* language:

DFA for (1001 + 110 + 11)* language

Similar threads

  • Programming and Computer Science
Replies
1
Views
694
  • Programming and Computer Science
Replies
2
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Programming and Computer Science
Replies
6
Views
12K
Replies
1
Views
14K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Programming and Computer Science
Replies
1
Views
2K
  • Sci-Fi Writing and World Building
2
Replies
52
Views
4K
  • Programming and Computer Science
Replies
2
Views
3K
Back
Top