# Tagged Questions

Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

46k views

### Difference between NFA and DFA

In very simple terms please, all resources I'm finding are talking about tuples and stuff and I just need a simple explanation that I can remember easily because I keep getting them mixed up.
576 views

### Eilenberg's rational hierarchy of nonrational automata & languages

In the preface to his very influential books Automata, Languages and Machines (Volumes A, B), Samuel Eilenberg tantalizingly promised a Volume C dealing with "a hierarchy (called the rational ...
12k views

### Why does this FSM accept binary numbers divisible by three?

This finite state machine (FSM) accepts binary numbers that are divisible by three. In theory the states should equal to the value $n$ mod $3$, but how does this work for binary numbers? What I don't ...
382 views

### Proof that an automaton stops

I discovered an automaton that produced interesting, random-seeming patterns. The rule was as follows. Given a grid of points, some occupied and some not, and a current point and a previous point; ...
755 views

### Why is it undecidable whether two finite-state transducers are equivalent?

According to the Wikipedia page on finite-state transducers, it is undecidable whether two finite-state transducers are equivalent. I find this result striking, since it is decidable whether two ...
339 views

### What is the class of languages accepted by DFAs whose transition monoids are transitive permutation groups?

In the Wiki page A permutation automaton, or pure-group automaton, is a deterministic finite automaton such that each input symbol permutes the set of states. ..... A formal language is p-regular (...
274 views

### Does there exist a universal pushdown automaton?

Let $\Sigma$ be a fixed alphabet and let $PDA(\Sigma)$ be the set of all Push-Down-Automata (PDA's) having input alphabet $\Sigma$. Is there an alphabet $S$ and a function $f:PDA(\Sigma) \to S^∗$ such ...
127 views

### Existence of NFA for this language

I'm given a task to find (and prove) such language $L$ in the alphabet $\Sigma = \{a,b\}$ with all words less than $1000$ in length, for which any DFA/NFA will have more than $10^{10}$ of states. For ...
475 views

216 views

### Density of black cells in rule 110

Is there a way to compute the limit of the ratio (number of black cells)/(number of white cells), in the rule 110 or rule 30 automaton? With initial state = 1 black cell. Simulation of first 120000 ...
123 views

### Can this set of rules perform all Boolean operations?

I never worked in this field before, I just thought about this set of rules and never saw something similar before. I apologise if I don't use the right mathematical vocabulary for my question. ...
120 views

### Describe and count the set of sequences containing $20$ or $02$

Let $X = \{ 0,1,2 \}$ be a ternary alphabet and denote by $X^*$ the set of finite sequences (i.e. strings) with three symbols. For $w \in X^*$ with $n$ the length of $w$ and $w = w_1 w_2 \cdots w_n$ ...
328 views

### Automata theory on infinite words: any video lectures?

I am fun of automata theory. Can you suggest good video lectures on the subject? (there is a good one here, but it is accessible from RWTH University only)
112 views

### This proof in my textbook involving the pumping lemma appears incorrect - is it?

It states Let $B$ be the language $\{0^n1^n2^n | n \geq 0\}$. We use the pumping lemma to prove that $B$ is not regular. The proof is by contradiction. Assume to the contrary that $B$ is regular. ...
3k views

### Finite Automaton that accepts only the words baa,ab, abb and no other strings longer or shorter

I am trying to understand the answer here for FA that accepts only the words baa, ab, abb and no other strings longer or shorter....
12k views

85 views

### Enhancing the monoid structure over a finite alphabet to prove Arden's rule

Suppose you have a finite-state, deterministic automaton, that you wish to convert to a regular expression. A common method, perhaps easier to apply by hand that Yamada's algorithm, is to reduce the ...
60 views

### proving that $L_\text{almost}$ is a regular language

Let it be L, a regular language. we will define: $L_\text{almost} = \{ w'\mid \exists w\in L\ w' \text{ is almost similar to }w \}$ a word $w'$ is almost similar to $w$ if they are in the same length,...
89 views

### Showing that 2 languages are context free

I have these 2 languages: $$L_1 = \left\{a^ib^jc^k: k\ge i+j\right\}\\ L_2 = \left\{w_1cw_2 : w_1,w_2\in\{a,b\}^\ast\land |w_1|_a = |w_2|_a\right\}$$ How can I determine that they are context free ...
Is my attempt is true or where am I wrong? DFA : The set of strings over $\{a, b\}$ that have odd length or end with $aaa$.