As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [finite-automata]

Questions about finite automata, an elementary automaton model with finite memory. It is equivalent to regular languages and the basis for many more complex models.

1,702 questions
Filter by
Sorted by
Tagged with
734 views

### epsilon-NFA to DFA conversion - What will be the final states and do we need to create empty state in DFA?

Source of this question and problem: https://www.javatpoint.com/automata-conversion-from-nfa-with-null-to-dfa This is the question: So in this figure there are my 1 confusion-: Don't we need a empty ...
• 37
2k views

### When you convert epsilon NFA to NFA, how do you decide the final states of resultant NFA?

The question is-: THIS is the transition table for NFA-: Final result as shown in youtube video. https://www.youtube.com/watch?v=GjLiXk0imi0&list=PLENQMW_c1dimRCKF3bjUqHaH8dvJkapSw&index=49 ...
• 37
58 views

### What does DFA that accepts at least 1 a or at least 1 b mean?

What are the language accepted by this DFA? The truth table of OR-: But I am unable to deduct what this dfa will accept? Say-: P=at least 1 a Q=at least 1 b So DFA should accept both ab. Or in ...
1k views

### Regular expression for set of all strings containing no 3 consecutive 0s?

The answer is $1^*01^*01^*+1^*(0+00+\in)1^*$ If I had to rephrase my question, it would be how to approach regular expression problems? Is it all about practice? How do I understand what the regular ...
1 vote
227 views

### NFA has power to be in several states at once implies NFA has ability to guess about its input. How?

I agree that NFA has power to be in several states at once. It probably means that on same input, NFA can be on multiple states. But what I can't understand is how can we conclude from this that "...
• 51
719 views

### DFA for {w|w contains a substring of length at most 5 that has at least three 1's}

I have thought about this problem, but cannot come up with a convincing answer since I think this problem has too many states too consider. The accepting states can be length 5 substring and 3 1's, ...
1 vote
111 views

### conversion of epsilon NFA to NFA

I was given below task: Eliminate Epsilon-transitions in below automata My solution: Is it correct that stage 1 is actually one of the final stages? How does it work in given example? We have ...
1 vote
38 views

### conversion of NFA to DFA (omitted states)

I've been given following task: Determine the following nondeterministic automaton (omit unreachable states, if they appear during construction) My solution to this: Would like to ask for a ...
50 views

### Problems with simulating NFA with DFA

I have this NFA: I want to simulate it with a DFA, thus I have the states {1}, {2}, {3}, {1,2}, {1,3}, {2,3} and {1,2,3}. Usually I look at every state and find out in which state I could end up when ...
71 views

• 163
29 views

### How can I implement a Deterministic finite automaton which accepts

Problem: implement a Deterministic finite automaton which accepts 01 ∪ (2∪10*2)* ∪ <- is union symbol I have a lot of problem trying to implement that DFA, the union symbol always confuse me Can ...
3k views

### Construct a DFA accepts set of all strings that begins with 01 and end with 11

I have drawn the DFA for language L1 containing strings starting with 01 and language L2 containing strings ending in 11. For the final DFA, I have concatenated both DFA's. The finals DFA does not ...