Questions tagged [automata-theory]

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

Filter by
Sorted by
Tagged with
9
votes
4answers
2k views

Proving the set of powers of 2 over ternary alphabet to be non regular.

It's simple to see that the powers of 2 over alphabet {0,1} is regular because $10^*$ is a regular expression for it. But the powers of 2 represented in ternary appears to be non regular. Pumping ...
9
votes
2answers
8k views

Why is non-determinism (Push-down automata) necessary?

I would like to know why for the recognition of context-free languages only non-deterministic push-down automata (DPA=NPDA) work. Why do deterministic push-down automata (DPDA) not recognize such ...
9
votes
4answers
2k views

Why are linear bounded automata not as popular as other automata?

In my experience, context-sensitive languages and linear bounded automata are frequently skipped or breezed over in computability theory courses, and are even left out of some notable text books, ...
9
votes
3answers
297 views

Class of languages recognizable by single-tape 3-state TMs

I have for a while been curious about Turing Machines with exactly one tape and exactly 3 states (namely the start state $q_0$, the accept state $q_{accept}$, and the reject state $q_{reject}$). Note ...
9
votes
3answers
428 views

Continuous mathematics and formal language theory

Whether there are some results on solving formal languages problems using mathematical analysis, continuous mathematics. For example, solving the intersection non-emptiness problem for a context-free ...
9
votes
2answers
327 views

Generalizing Brzozowski's DFA minimization algorithm to finite automata with different classes of accepting states?

Brzozowski's algorithm for converting a DFA into an equivalent minimum-state DFA is remarkably simple: if $R(D)$ denotes the NFA formed by reversing all the edges in a DFA $D$, making the old start ...
9
votes
2answers
296 views

Number of minimal DFAs of size at most $m$?

Let $\Sigma$ be an alphabet of size $2$, and consider minimal DFAs whose size is bounded by at most $m$. Let $f(m)$ denote the number of different such minimal DFAs. Can we find a closed-form ...
9
votes
1answer
407 views

Measurable language which is not $\omega$-regular

Let $\Sigma$ be a finite alphabet and let $\Sigma^\omega$ be the set of all infinite words over $\Sigma$. Consider $$ d(x,y):=2^{-\min(n \in \Bbb N_0:x_n\neq y_n)} $$ to be the metric on $\Sigma^\...
9
votes
1answer
292 views

Transition monoid membership for DFAs

Given a complete DFA $A=(Q, \Gamma, \delta, F)$, we can define a collection of functions $f_a$ for each $a\in \Gamma$and with $f_a:Q\rightarrow Q$, $f_a(q)=\delta(q, a)$. We can generalize this notion ...
9
votes
1answer
829 views

DFA intersection algorithm for special cases

I'm interested in efficient algorithms for DFA intersection for special cases. Namely, when the DFAs to intersect obey a certain structure and/or operates on limited alphabet. Is there any source ...
9
votes
1answer
158 views

Containment problem of an acyclic NFA in an NFA

Let $A$ and $B$ be NFAs, such that $A$ is acyclic. In the general case, deciding whether $L(A)\subseteq L(B)$ is $PSPACE$-hard. However, since $A$ is acyclic, we know that for every $w \in L(A)$, it ...
9
votes
1answer
267 views

Directed multigraphs as minimal automata

Given a regular language $L$ on alphabet $A$, its minimal deterministic automaton can be seen as a directed connected multigraph with constant out-degree $|A|$ and a marked initial state (by ...
9
votes
1answer
191 views

Do bounded-visit nondeterministic linear bounded automata recognize only regular languages?

Do bounded-visit nondeterministic linear bounded automata recognize only regular languages? By a nondeterministic linear bounded automaton (nLBA) I mean a single-tape nondeterministic Turing machine ...
9
votes
1answer
275 views

Turing Machines as Coalgebras

I'm looking to write a survey on the method of representing the dynamics of state-based computation within the framework of coalgebras. So far I've managed to find papers on coalgebra representations ...
9
votes
1answer
159 views

Generalisation of the statement that a monoid recognizes language iff syntactic monoid divides monoid

Let $A$ be a finite alphabet. For a given language $L \subseteq A^{\ast}$ the syntactic monoid $M(L)$ is a well-known notion in formal language theory. Furthermore, a monoid $M$ recognizes a language $...
9
votes
2answers
429 views

Are there families of formal languages known to be truly PAC learnable?

I specifically mean language families that admit arbitrarily long strings -- not conjunctions over n bits or decision lists or any other "simple" language contained in {0,1}^n. I am asking about "...
9
votes
1answer
220 views

Automata recognizing $X^*$ for a finite code $X$

Let $\Sigma$ be a finite alphabet. A code $X$ over $\Sigma$ is a subset of $\Sigma^*$ such that each word in $X^*$ can be uniquely represented as a concatenation of words in $X$. A code $X$ is finite ...
9
votes
0answers
79 views

Reference request: DFA linear-time minimization

What is the most complicated kind of deterministic finite-state automaton that can be minimized in $O(n)$ time? Here’s what I’ve been able to find so far: The acyclic case has been solved. So any ...
9
votes
0answers
175 views

Shortest string in the intersection of regular languages

Inspired by https://codegolf.stackexchange.com/questions/53310/shortest-universal-maze-exit-string Each of the 138,172 valid mazes can be represented as a DFA with 9 states (including starting and ...
9
votes
0answers
494 views

What exactly are Moore machines?

Ok, don't be scared by the title - it is not that I don't know the concept of a Moore machine, or basic FSM concepts in general. However, I think that the term "Moore machine", despite being ...
8
votes
4answers
483 views

Constraints on sliding windows

Let $L\subseteq \Sigma^*$ be a language of finite words and $n>0$ some integer. I would like to know if anything is known on the time and space complexity with respect to $n$ to check for ...
8
votes
3answers
793 views

1-way Quantum Finite Automata Example Question

I'm attempting to clarify my understanding in the example presented in Section 2.2 of 1-way Quantum Finite Automata: Strengths Weaknesses and Generalizations (this alternative link may also be useful)....
8
votes
1answer
370 views

Lower bound for NFA accepting 3 letter language

Related to a recent question (Bounds on the size of the smallest NFA for L_k-distinct) Noam Nisan asked for a method to give a better lower bound for the size of an NFA than what we get from ...
8
votes
2answers
525 views

What's the simplest to implement of all decent LTL-to-Buchi translation or other LTL verification algorithms?

I'm writing a toy modelchecker, and I'm at the point where it's time to implement LTL to Buchi automata translation. For a variety of obvious reasons, I wish the algorithm to be simple :) e.g. I want ...
8
votes
1answer
449 views

Tool for translating PDAs to CFGs

We know that all push down automata are representable using context-free grammars. Furthermore, there is an algorithm to construct a CFG from any PDA (e.g. Sipser's proof in intro to theory of ...
8
votes
1answer
336 views

Can we efficiently enumerate the words accepted by a DFA by order of increasing weight?

Fix a deterministic finite automaton $A$ defining a regular language on the alphabet $\Sigma = \{0, 1\}$, and call the (Hamming) weight of a word $w \in \Sigma^*$ its number of $1$'s. Given a length $...
8
votes
1answer
738 views

NFA to DFA Powerset Construction : A Partial determinization algorithm with trade-off between running time and size for the resulting automata?

Given a NFA $N$ and its equivalent DFA $D$ resulting from the total determinization of $N$ (using powerset construction, for example), the following properties hold for $N$, $D$ and for any word $w$ : ...
8
votes
1answer
396 views

What can I say about the Parikh map of a CSL?

Write $\Psi$ as the Parikh map--i.e., $\Psi(w) = \{(\#_\sigma(w))_{\sigma\in \Sigma}\vert w\in L\}$, where $\#_\sigma(w)$ is the number of times $\sigma$ appears in $w$. It's well-known that, for a ...
8
votes
1answer
167 views

A conjecture related to the Cerny conjecture - counterexample/reference request

The Cerny conjecture is the statement that any synchronizing automaton with $n$ states has a synchronizing word of length at most $(n-1)^2$. The best current upper bound for the length of a ...
8
votes
0answers
128 views

Determining if transducer automaton has two states with intersecting images, without minimizing?

I work (in implementation!) with deterministic finite state automata with input and output; i.e. there are transitions (start state,input letter)$\to$(new state,output letter). Thus every state gives ...
8
votes
0answers
1k views

Data structures for Finite Automata

I am a Control Engineer and I have been working on Discrete Event Systems and Supervisory Control, based on Finite Automata Theory. My problem is to represent large automata (about $2 \times 10^6$ ...
7
votes
3answers
661 views

Algorithm for ranking members of a regular language?

A little while back, I was reading a paper that mentioned a method for computing an integer 'rank' for a particular string $s \in L$ where $L$ is some regular language. This rank uniquely determines ...
7
votes
5answers
409 views

NP-complete decision problems on deterministic automata

Do you know any NP-complete decision problems on deterministic automata? Most NP-complete problems that come to my mind are either (see, or here) graph theoretical, or involve some string rewriting or ...
7
votes
2answers
8k views

Difference between infinite state machines and turing machines

Finite state machines (FSM) are strictly less powerful than turing machines (TM). But this is not the case with infinite state machines (ISM). For example, every TM can be embedded into some ISM. ...
7
votes
2answers
721 views

In the context of regular languages, must the alphabet be finite?

In The Theory of Parsing, Translation, and Compiling, Volume I, Section 0.2.1 (p.15 / 1972), Aho and Ullman casually write that "[a]n alphabet need not be finite or even countable, but for all ...
7
votes
3answers
458 views

Where does the modern canonical version of the Turing machine come from?

Turing's original 1936 description of his a-machine differs in several respects from the Turing machine I studied at university, leading me to questions: The Turing machine I learned about was ...
7
votes
1answer
241 views

Measurability of an $\omega$-regular language

It the previous question of mine I put a reference which shows that any $\omega$-regular language over the alphabet $\Sigma$ is a Borel subset of $\Sigma^\omega$. I am not sure whether the reference I ...
7
votes
1answer
1k views

Photo of «Introduction to automata…» by Hopcroft and Ullman '79 cover?

Where can I get the photo of “Introduction to automata theory, languages and computation” by Hopcroft and Ullman '79 (first edition) cover in order to be able to read all the phrases placed on the ...
7
votes
2answers
297 views

Smallest representatives of a quotient by an equivalence relation

Background Let $\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$ be a minimal DFA for a regular language $L$ such that $|Q|=n$, and let $\equiv_L$ be the relation given by $$x\equiv_Ly\text{ iff for all $u$: }xu\...
7
votes
1answer
209 views

Finding a minimal DFA whose language has a desired intersection with another

Suppose I have regular languages $B \subseteq A$, with corresponding (known) minimal deterministic finite automata $M_A, M_B$. I would like to find another regular language $C$ such that $B = A \cap ...
7
votes
1answer
418 views

Is this a regular relation?

I'm a linguist (and not a computer scientist!) investigating a new sort of linguistic formalism for mapping phonological strings into other strings - and I'm wondering if it's a regular relation that ...
7
votes
1answer
129 views

Isomorphism of ‘ordered’ DAGs / acyclic semiautomata

I am wondering what is known about the isomorphism problem on ordered DAGs, in particular how to find a canonical representative modulo isomorphism. By ordered I mean that each vertex has a list of ...
7
votes
2answers
183 views

Closure of Recognizable Languages under Kleene Star: Algebraic Proof?

Let $Rec(\Sigma)$ be the class of languages over $\Sigma^*$ recognizable by finite monoids. To show that $Rec(\Sigma)$ is closed under Kleene star, one would usually refer to the equivalence of ...
7
votes
2answers
484 views

Are all turing machines paths predictable?

I was recently studying partial solutions to the halting problem and came across the problem which I discuss below. In particular I was studying when it was computable to tell if a turing machine has ...
7
votes
1answer
114 views

Extensional characterization of non-deterministic finite state transductions

I recently became aware of the rather appealing characterization of deterministic word-to-word transductions as word functions with bounded variation (see e.g. [1]). This coincides with the set of ...
7
votes
2answers
706 views

Maximal munch rule issue for lexers: is detection decidable?

Edit: I realise that one of my problems is that I don't have a clear definition of my problem, which makes the question of whether it is detectable hard to answer. I'm therefore already happy with ...
7
votes
1answer
180 views

Automata : Language Containment, Minimality & Graph Homomorphism

Given two DFAs $A$ and $B$ defined on the same alphabet, a (graph) homomorphism $h:A \rightarrow B$ from $A$ to $B$ is a mapping of the states of $A$ into the states of $B$ such that : if the state $...
7
votes
1answer
478 views

Shortest string in the intersection of a context-free language and a regular language

For a language $X$, define $ss(X) = \min_{x\in X} |x|$, the length of the shortest string in $X$. For simplicity, we define $ss(\emptyset)=0$. Let $L$ be a context-free language generated by a context-...
7
votes
2answers
244 views

A tool for minimal NFA computation

It is well known that minimizing an NFA for a fixed regular language is $PSPACE-Complete$. As far as I know, there are no better than trivial algorithms for minimizing such NFA, but there's a little ...
7
votes
1answer
136 views

Random Deterministic Automata

I am familiar with the term of random graphs, such as $G(n,p)$- a distribution over simple undirected graphs with $n$ vertices, where each edge appears in a graph w.p. $p$. That is, each graph $G=(V,E)...

1 2
3
4 5
8