# 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,358 questions
Filter by
Sorted by
Tagged with
34 views

### Finite state machine for a modified traffic controller

Consider a traffic light controller for an intersection of a main street and a smaller street. Both streets are one-way streets. The intersection has two traffic lights, one for each street. In normal ...
28 views

### How to deal with sets in NFA?

I have a transition system that I'm converting to an NFA. In the TS, I have a trace of {b} {a, b} {a, b, c}. How would I handle these sets in the NFA? In other words, what would be the path to follow ...
132 views

### How do I solve these questions regarding homomorphism?

Questions: Give an example of a homomorphism, using the same alphabet, Σ, for both languages A and B. Now, give a second example of a homomorphism but this time using two different alphabets, Σ and ...
110 views

### Prove $\epsilon(S\cap T)\subseteq S \cap T$

Suppose there are sets $S\subseteq Q, T\subseteq Q$ such that $T=\epsilon (T),S=\epsilon (S)$. Prove $\epsilon(S\cap T)\subseteq S \cap T$ Definition of $\epsilon$- closure for epsilon NFA is: ...
497 views

### NFA for all strings not containing 1010

if I want to design a NFA (that's NOT A DFA) that accepts the set of all strings that do not contain the substring 1010, is this correct? because I can just accept 1010 by capturing it in the starting ...