# Questions tagged [automata-theory]

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

54 questions
Filter by
Sorted by
Tagged with
23k views

### Books on automata theory for self-study

I need a finite automata theory book with lots of examples that I can use for self-study and to prepare for exams.
1k views

### Deciding emptiness of intersection of regular languages in subquadratic time

Let $L_1,L_2$ be two regular languages given by NFAs $M_1,M_2$ as input. Assume we would like to check whether $L_1\cap L_2\neq \emptyset$. This can clearly be done by a quadratic algorithm which ...
733 views

305 views

### Name this digraph

I am trying to track down the name of this digraph and some references: You take all members of the transformation semigroup on $n$ elements, $T_{n}$. For two members $x$ ,$y$ ; if $x$ is in the ...
234 views

### Automata and a kind of pumping lemma on state transition function

We encountered this question as an exercise in a Büchi automata book a couple of decades ago, and back then gave a few tries thinking that it should be easy. But haven't seen a solution. My ...
324 views

### Inductive definition of ECTL*: how are recursive formulas forbidden?

In , the extended computation tree logic ECTL* is inductively defined as the propositional formulas over all E($A(F_1,..F_n)$), where E is the existential path quantifier and $A$ some Büchi ...
887 views

### The class CFL\cap co-CFL

Is anything nontrivial known about the class $\mathrm{CFL}\cap \mathrm{coCFL}$? In particular, is it known whether $\mathrm{CFL}\cap \mathrm{coCFL} = \mathrm{DCFL}$ (certainly the reverse containment ...
Possible Duplicate: Is finding the minimum regular expression an NP-complete problem? Let's suppose that I have an unknown language $\mathcal L$, I know only two (particularly large) sets of ...