Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

# Questions tagged [automata]

Questions about mathematical devices that read an input stream symbol by symbol and use a state transition map to produce an output stream, maybe using secondary storage.

1,633 questions
Filter by
Sorted by
Tagged with
27 views

• 5
40 views

### Finding an algorithm that decides given 2 regular expressions $E_1$ and $E_2$ and a non-negative integer $k$, whether $|L(E_1) \backslash L(E_2)| = k$

Find an algorithm that decides, given 2 regular expressions $E_1$ and $E_2$ and a non-negative integer $k$, whether $|L(E_1) \backslash L(E_2)| = k$. I know that regular expressions are closed under ...
• 369
84 views

### Does computer use NFA or DFA?

I am now learning about automation and I am wondering if personal computers use NFAs or DFAs. I believe it uses a DFA since when we are clicking on something it is in a way determined what will happen....
• 103
59 views

### If language $P$ is not regular, is $\{ w \in \Sigma ^* : |w| \geq 1000 \}\cup P$ regular necessarily?

Prove or refute. Let $L = \{ w \in \Sigma ^* :\ |w| \geq 1000 \}$. Let $P$ be a non-regular language. Then $L \cup P$ is regular necessarily. I think it is true, but I don't have any idea ...
• 115
1 vote
36 views

### In how far is an automaton allowed to grow based on the length of its input?

Recently, I've written a draft article on the computational power of Petri-nets. An understanding of Petri-nets isn't really essential to answering this question, but I'll still note that the ...
31 views

### NP Completness and NP Hard

i need some help regaridng this text: CLIQUE = { G, k | G is an undirected graph that contains a clique with k nodes } The textbook proves that CLIQUE is NP-complete. Define the language TWO-CLIQUES ...
• 13
51 views

• 313