Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [dfa]

Questions about deterministic finite automata

9
votes
0answers
99 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 ...
5
votes
1answer
93 views

Is Bayes optimal RL of a finite set of DFAs feasible?

Let $Q$ be a finite set of states, $\Sigma$ a finite alphabet, $q_0\in Q$ the start state and $F\subseteq Q$ the set of accepting sets. Let $\{\delta_k:Q\times\Sigma\rightarrow Q\}_{k=1}^n$ be a set ...
-1
votes
1answer
86 views

When designing a DFA, am I allowed to design two separate Machines and perform an Intersection on them? [closed]

I am trying to design a DFA s.t. The set of strings in x ∈ {0, 1}∗ such that the number of zeros is a multiple of 3 and the number of one's is even. My idea was to create two Machines M1 = (Q1, Σ, δ1,...
3
votes
1answer
230 views

NFA to 2DFA: what are the upper and lower bounds?

Suppose that one has an NFA (from, say, a regular expression). What is the state complexity of turning it into a 2DFA?
-1
votes
1answer
57 views

Non equivalent states shortest word [closed]

My textbook contains a theorem that if you have a DFA and two states that are not-equivalent, then there is a differentiating word that has length smaller than amount of states in that DFA. How do we ...
3
votes
0answers
43 views

Structural property of DFAs/NFAs accepting LTL-definable languages

I consider LTL on finite words. In this context, there are a couple of nice equivalence results for a language L: L is LTL-...
9
votes
1answer
461 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$ : ...
7
votes
1answer
155 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 $...
9
votes
2answers
255 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 ...
7
votes
2answers
165 views

Finite Automata with succinct representation of chains of states

Consider a kind of automata similar to common DFAs or NFAs where it is possible to represent succinctly linear chains of states. In other words, an automaton like this: could be represented in this ...
16
votes
2answers
572 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, ...
-4
votes
1answer
1k views

How to check if a the language represented by a DFA is finite [closed]

I am studying regular languages and D FA. I have implemented D FA in Java. I have to write a function which tells if the language represented by a D FA is finite or not. I need a method or algorithm ...
3
votes
5answers
690 views

How to constrain a finite automaton (NFA and DFA) to a tree?

I have a finite automaton by the standard model Hopcroft & Ullman define: $$ M = (Q, \Sigma, \delta, q_0, F) $$ Where $\delta$ is the transition function mapping $Q \times \Sigma \mapsto Q$, such ...
6
votes
2answers
227 views

FSM transducer sequential composition decidability

this is a followup/ sequel to this recent question which was answered, this one presumably significantly harder. consider a deterministic FSM transducer $F$ and its mapping $F(x)$ of an input word $x$....
10
votes
1answer
212 views

Is it decidable whether the output length of a transducer is bounded by the input length?

The transducers considered here are those Wikipedia calls finite state transducers. The behavior of a transducer $T$, that is, the relation it computes, is written $[T]$: a word $y$ is an output for $...
1
vote
1answer
709 views

What is the relation/difference between axiomatic and denotational semantics one one side, and the data flow analysis(DFA) on the other sied?

I am supposed to write a small paper about DFA in OOP for a CS class in theory. But I am required to connect that (DFA) to axiomatic and denotational semantics! I read few resources about axiomatic/...
5
votes
1answer
137 views

When does automaton stay unchanged after string homomorphism?

Suppose we have a string homomorphism $\varphi: \Sigma \rightarrow \Sigma^*$. Consider the languages in $\varphi(\Sigma^*)$ whose letters are elements of $\varphi(\Sigma)$, so here I do not want to ...
23
votes
1answer
732 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 ...
9
votes
1answer
637 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 ...
-1
votes
1answer
880 views

How to XOR automata? [closed]

Say we have 3 DFAs. We know how to OR, AND, or NOT them. But how does one XOR them? There is not one single mention of this online. x XOR y XOR z = ((x|y)(~x|y)|z) (~((x|y)(~x|y))|z). This is way too ...
15
votes
1answer
299 views

Separating words with random DFAs

One of the interesting open problems about DFAs listed in Are there any open problems left about DFAs? is the size of a DFA required to separate two strings of length $n$. I am curious if there any ...
2
votes
0answers
297 views

Composition of regular expressions with lookahead into DFAs

Let's say we have a regular expression ("a" | "b"(~!"b"))*, written in Perl or other similar languages that support lookahead, which should match a list of a and b's where b's are not followed by b's. ...
58
votes
10answers
6k views

Are there any open problems left about DFAs?

After studying deterministic finite state automata (DFA) in undergrad, I felt they are extremely well understood. My question is whether there is something we still don't understand about them. I don'...
23
votes
1answer
520 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 ...
4
votes
1answer
211 views

Are there any books containing collections of automata problems?

You can find specialized books consisting entirely or problems from particular math domains (e.g. linear algebra, polynomials, combinatorics), but I've yet to find such a book for automata of any kind....
2
votes
1answer
454 views

What are good conferences for algorithms about finite automata?

I am writing a research paper, which describes some properties about finite automata. It also provides a couple of algorithms that can measure some aspects of the properties. Could you point out some ...
5
votes
0answers
191 views

Exploring a DFA, with no feedback

Let $M=(\Sigma,S,s_0,\delta)$ be an (unknown) deterministic finite-state automaton (DFA), with alphabet $\Sigma$, statespace $S$, start state $s_0 \in S$, and transition relation $\delta$. I want to ...
3
votes
1answer
195 views

Finding self-similar homomorphisms of a FSM transducer

Consider a special case of homomorphisms of FSM transducers (or "generalized sequential machines" in [1]). Let $F$ be a transducer accepting a language $L$, and let $h(x)$ be a homomorphism function ...
4
votes
3answers
382 views

How to minimize a FSM transducer?

In contrast to FSM minimization which is well studied with various algorithms, theorems and has many practical applications, I'm looking for any nontrivial insight, analysis and references to the ...
12
votes
2answers
3k views

Algorithm for converting very large NFA to DFA

I have really large Non-deterministic finite automaton and I need to convert it to the DFA. By large I mean 40 000+ states. So far I have done some experiments and programmed the default algorithm ...
6
votes
0answers
141 views

Are k+1 heads better than k for multiread finite automata?

Consider the deterministic (resp. non-deterministic) one-way finite automaton that is defined in the usual way except that it has k heads and in each step can decide which head to move. (It is allowed ...
14
votes
2answers
841 views

minimizing size of regular expression for finite sets

It is known that minimizing the size of a regular expression is PSPACE-complete even if we have a DFA as the language's specification. What are the results if the language is finite? One can ...
9
votes
1answer
326 views

Multi-language DFA minimisation

I'm interested in a slight generalisation of DFA. As usual we have state-set $Q$, finite alphabet $\Sigma$, a $\Sigma^*$-action defined on $Q$ by $\delta : Q\times\Sigma\rightarrow Q$, and initial ...
-1
votes
0answers
115 views

How does “δ:Q×Σ→Q” read in the definition of a DFA (deterministic finite acceptor)? [closed]

How do you say "δ:Q×Σ→Q" in English? Describing what "×" and "→" mean would also help.
12
votes
1answer
675 views

The Cost of an Equivalence Query for DFA

Inspired by this question, I am curious about the following: What is the worst-case complexity of checking whether a given DFA accepts the same language as a given regular expression? Is this ...
11
votes
1answer
4k views

What algorithms exist for construction a DFA that recognizes the language described by a given regex?

All of my textbooks use the same algorithm for producing a DFA given a regex: First, make an NFA that recognizes the language of the regex, then, using the subset (aka "powerset") construction, ...
237
votes
11answers
94k 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 ...
6
votes
3answers
871 views

Complexity lower bound for regular languages

Suppose I have a regular language $L$, and I would like to lower-bound the complexity of deciding membership in $L$. Suppose I know that the minimal DFA for $L$ has $N$ states. I would like to claim ...
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,...
16
votes
1answer
976 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 ...
5
votes
5answers
689 views

Is it possible to represent a regular expression with bounded captures using a DFA and O(1) additional processing?

It's well known that a regular expression can be converted to a non-deterministic finite state automaton, which can in turn be converted in to a deterministic finite state automaton. These DFAs can ...
9
votes
2answers
284 views

Are non-deterministic tree-walking automata stronger than deterministic ones?

Update: It seems this problem has been studied and solved recently, see this wiki article: http://en.wikipedia.org/wiki/Tree_walking_automaton And also this survey: http://www.mimuw.edu.pl/~bojan/...
2
votes
1answer
442 views

upper bound on the size of a DFA for A|B given the DFAs for A and B?

Given RegEx A and B where the size of the compiled DFAs are m and ...
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 ...
16
votes
3answers
2k views

Can a nondeterministic finite automata (NDFA) be efficiently converted to a deterministic finite automata (DFA) in subexponential space/time?

Twenty years ago, I built an regular expression package that included conversions from regular expressions to a finite state machine (DFA) and supported a host of closed regular expression operations ...