Questions tagged [automata-theory]

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

244
votes
11answers
95k views

What is the enlightenment I'm supposed to attain after studying finite automata?

I've been revising Theory of Computation for fun and this question has been nagging me for a while (funny never thought of it when I learnt Automata Theory in my undergrad). So "why" exactly do we ...
43
votes
5answers
6k views

Is the Chomsky-hierarchy outdated?

The Chomsky(–Schützenberger) hierarchy is used in textbooks of theoretical computer science, but it obviously only covers a very small fraction of formal languages (REG, CFL, CSL, RE) compared to the ...
41
votes
10answers
15k views

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

Real computers have limited memory and only a finite number of states. So they are essentially finite automata. Why do theoretical computer scientists use the Turing machines (and other equivalent ...
37
votes
14answers
22k views

How practical is Automata Theory?

There is always a way for application in topics related to theoretical computer science. But textbooks and undergraduate courses usually don't explain the reason that automata theory is an important ...
37
votes
9answers
18k views

What is the difference between non-determinism and randomness?

I recently heard this - "A non-deterministic machine is not the same as a probabilistic machine. In crude terms, a non-deterministic machine is a probabilistic machine in which probabilities for ...
35
votes
6answers
5k views

Regular expressions aren't

Ask even someone with a background in computer science what a regular expression is, and the answer is likely to go beyond the constraint of being within reach of a finite-state automaton. For ...
33
votes
11answers
22k 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.
31
votes
1answer
703 views

Eilenberg's rational hierarchy of nonrational automata & languages — where is it now?

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

Are there “small” machines which can efficiently match regular expressions?

It's well-known that a regular expression can be recognized by a nondeterministic finite automaton of size proportional to the regular expression, or by a deterministic FA which is potentially ...
30
votes
2answers
2k views

Is {$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} non-context-free?

Is the language {$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} context-free or not? I realized that I have encountered almost all variants of this question with different conditions about the ...
28
votes
3answers
3k views

Known algorithms to go from a DFA to a regular expression

I was wondering whether there is a ``better'' (I will explain in what sense) algorithm to start from a DFA $\mathcal{A}$ and construct a regular expression $r$ such that $L(\mathcal{A})=L(r)$, than ...
28
votes
2answers
2k views

How many DFAs accept two given strings?

Fix an integer $n$ and alphabet $\Sigma=\{0,1\}$. Define $DFA(n)$ to be the collection of all finite-state automata on $n$ states with starting state 1. We are considering all DFAs (not just connected,...
27
votes
2answers
1k views

Conditions for NFA universality

Consider a nondeterministic finite automata $A = (Q, \Sigma, \delta, q_0, F)$, and a function $f(n)$. Additionally we define $\Sigma^{\leq k} = \bigcup_{i \leq k} \Sigma^i$. Now lets analyze the ...
26
votes
4answers
1k views

Is there a non Turing-complete model of computation whose halting problem is undecidable?

I cannot think of any such model, maybe some form of typed lambda calculus? some elementary cellular automaton? This would almost disprove Wolfram's "Principle of Computational Equivalence": ...
25
votes
4answers
2k views

DFA intersection in subquadratic space?

The intersection of two (minimal) DFAs with n states can be computed using O(n2) time and space. This is optimal in general, since the resulting (minimal) DFA may have n2 states. However, if the ...
25
votes
2answers
1k views

Context Sensitive Grammars and Types

1) What, if any, is the relationship between static typing and formal grammars? 2) In particular, would it be possible for a linear bounded automaton to check whether, say, a C++ or SML program was ...
24
votes
1answer
462 views

complexity of the half language

For any language $L$ over $\Sigma^*$, define $$L_{1/2} = \{x \in \Sigma^* : xy\in L, y\in\Sigma^{|x|} \}.$$ In words, $L_{1/2}$ consists of all $x$ for which there is a $y$ of equal length such that $...
23
votes
1answer
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 ...
23
votes
1answer
775 views

Finding the smallest DFA that separates two words without using brute force search?

Given two strings x and y, I want to build a minimum size DFA that accepts x and rejects y. One way to do this is brute force search. You enumerate DFA's starting with the smallest. You try each ...
23
votes
1answer
546 views

Languages recognized by polynomial-size DFAs

For a fixed finite alphabet $\Sigma$, a formal language $L$ over $\Sigma$ is regular if there exists a deterministic finite automaton (DFA) over $\Sigma$ which accepts exactly $L$. I am interested in ...
22
votes
2answers
485 views

Testing whether letters can be scheduled to achieve a word in a regular language

I fix a regular language $L$ on an alphabet $\Sigma$, and I consider the following problem that I call letter scheduling for $L$. Informally, the input gives me $n$ letters and an interval for each ...
21
votes
4answers
5k views

Proof of the pumping lemma for context-free languages using pushdown automata

The pumping lemma for regular languages can be proved by considering a finite state automaton which recognizes the language studied, picking a string with a length greater than its number of states, ...
21
votes
1answer
354 views

For which regular expressions $\alpha$ is $\{ \beta \mid L(\alpha) = L(\beta) \}$ PSPACE-complete?

It is well known that the following problem is PSPACE-complete: Given regular expression $\beta$, does $L(\beta) = \Sigma^*$? What about determining equivalence to other (fixed) regular ...
20
votes
3answers
2k views

If an abstract machine can simulate itself, does that make it Turing complete?

For instance, in programming languages it's common to write an X-in-X compiler/interpreter, but on a more general level many known Turing-complete systems can simulate themselves in impressive ways (e....
19
votes
5answers
2k views

A special class of languages: “circular” languages. Is it known?

Define the following class of "circular" languages over a finite alphabet Sigma. Actually, the name already exists to denote a different thing it seems, used in the field of DNA computing. AFAICT, ...
19
votes
4answers
3k views

Where do most REGEX implementations fall on the complexity scale?

Most modern implementations of regular expressions, such as the ones in perl or .NET, go beyond the classical computer science definition of REGEXes with features like lookahead and lookbehind. Do ...
19
votes
3answers
1k views

Is the concept of the Turing Machine derived from automata?

I was just recently having a discussion about Turing Machines when I was asked, "Is the Turing Machine derived from automata, or is it the other way around"? I didn't know the answer of course, but I'...
19
votes
2answers
1k views

Status of Cerny Conjecture?

A DFA has a synchronizing word if there is a string that sends any state of the DFA to a single state. In ‘The Cerny Conjecture for Aperiodic Automata” by A. N. Trahtman (Discrete Mathematics and ...
19
votes
1answer
2k views

What is the number of languages accepted by a DFA of size $n$?

The question is simple and direct: For a fixed $n$, how many (different) languages are accepted by a DFA of size $n$ (i.e. $n$ states)? I will formally state this: Define a DFA as $(Q,\Sigma,\delta,...
19
votes
1answer
405 views

Conjecture about two counters automata

I would like to prove (or disprove) the following conjecture: Conjecture: a two counter automata (2CA) cannot decide the following language: $L = \{ n \mid $ the ternary and binary representations ...
18
votes
5answers
579 views

What notable automaton models have polynomially-decidable containment?

I'm trying to solve a particular problem, and I thought I might be able to solve it using automata theory. I'm wondering, what models of automata have containment decidable in polynomial time? i.e. if ...
18
votes
2answers
6k views

Finite automata that accept binary strings divisible by n

I'm working on a problem set for a class, and thought of a question related to what I was working on. Is there a minimum number of states that a finite automaton must have in order to accept binary ...
18
votes
2answers
701 views

Bounds on the size of the smallest NFA for L_k-distinct

Consider the language $L_{k-distinct}$ consisting of all $k$-letter strings over $\Sigma$ such that no two letters are equal: $$ L_{k-distinct} :=\{w = \sigma_1\sigma_2...\sigma_k \mid \forall i\in[k]...
18
votes
0answers
458 views

To what extent MSO = WS1S, when adding relations?

[This question has been asked on MathOverflow with no luck a month ago.] Let me first clarify my definitions. For a word $w \in \Sigma^*$, with $\Sigma =\{a_1, \ldots, a_n\}$, I define two ...
17
votes
1answer
2k views

computing the minimal NFA for a DFA

Many years ago I heard that computing the minimal NFA (nondeterministic finite automaton) from a DFA (deterministic) was an open question, as opposed to the vice versa direction which has been known ...
17
votes
5answers
1k views

Ambiguity and Logic

In automata theory (finite automata, pushdown automata, ...) and in complexity, there is a notion of "ambiguity". An automaton is ambiguous if there is a word $w$ with at least two distinct accepting ...
17
votes
3answers
1k views

Properties of Random Directed Graphs with Fixed Out-Degree

I am interested in properties of random directed graphs with fixed out-degree $d$. I am imagining a random graph model where each vertex chooses d neighbors (say, with replacement) u.a.r. ...
17
votes
2answers
236 views

A reference for a “more algebraic” approach to pushdown automata and CFLs?

In the Sakarovitch's book on automata theory, it is written in the introduction to the section on rationals in the free group that the material presented therein lays "the foundation of a truly ...
17
votes
2answers
416 views

Unary languages recognized by two-way deterministic counter automata

2dca's (two-way deterministic one-counter automata) (Petersen, 1994) can recognize the following unary language: \begin{equation} \mathtt{POWER} = \lbrace 0^{2^n} \mid n \geq 0 \rbrace. \end{...
16
votes
2answers
509 views

How small can a NFA be, compared to the minimal Unambiguous Finite Automaton (UFA) of the same regular language?

Unambiguous Finite Automatons (UFA) are special type of non-deterministic finite automatons (NFA). A NFA is called unambiguous if every word $w\in \Sigma^*$ has at most one accepting path. This ...
16
votes
1answer
1k views

Efficient concatenation of DFAs?

There is theoretical evidence that the naive cartesian-product construction for the intersection of DFAs is "the best we can do". What about the concatenation of two DFAs? The trivial construction ...
16
votes
1answer
905 views

Quadratic relationship between nondeterministic and deterministic space?

Savitch's theorem shows that $\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)$ for all large enough functions $f$, and proving that this is tight has been an open problem for decades. Suppose ...
16
votes
1answer
404 views

Can constant ambiguity reduce the state complexity of a regular languages?

We say that NFA $M$ is Constantly Ambiguous if there exist $k\in \mathbb{N}$ such that any word $w\in \Sigma^*$ is accepted by either $0$ or (exactly) $k$ paths. If automaton $M$ is constantly ...
16
votes
1answer
387 views

Are there variants of visibly pushdown automata that allow pushing of words onto the stack?

I'm wondering, are there any papers or research dealing with visibly pushdown automata, but allowing words, rather than single letters, to be pushed onto the stack. Alternately, a construction which ...
15
votes
1answer
537 views

Are DPDAs without a $\epsilon$ moves as powerful as DPDAs with them?

In the formal description of Deterministic Pushdown Automata, they allow $\epsilon$ moves, where the machine can pop or push symbols onto the stack without reading a symbol from the input. If these $\...
15
votes
2answers
611 views

Is there a well-defined division operation on finite automata?

Background: Given two deterministic finite automata A and B, we form the product C by letting the states in C be the cartesian product of states in A and states in B. Then, we choose transitions, ...
15
votes
1answer
331 views

Compared growth of the number of syntactic classes and Nerode classes.

For a language L ⊆ Σ^*, define the syntactic congruence ≡ of L as the least congruence on Σ^* that saturates L, i.e. : u ≡ v ⇔ (∀ x, y)[xuy ∈ L ↔ xvy ∈ L]. Now define the Nerode equivalence as the ...
14
votes
4answers
485 views

Hierarchies in regular languages

Is there any known "nice" hierarchy $L_0 \subseteq L_1 \subseteq L_2 \subseteq \dots$ (may be finite) inside the class of regular languages $L$? By nice here, the classes in each hierarchy capture ...
14
votes
3answers
735 views

The significance of state complexity in automata and regular languages?

I'm reading "Concatenation of Regular Languages and Descriptional Complexity" by Galina Jiraskova, 2009 on the state complexity resulting from concatenation of two regular languages ( by Galina ...
14
votes
2answers
556 views

Regular versus TC0

According to the Complexity Zoo, $\mathsf{Reg} \subseteq \mathsf{NC^1}$ and we know that $\mathsf{Reg}$ cannot count so $\mathsf{TC^0} \not\subseteq \mathsf{Reg}$. However it doesn't say if $\mathsf{...