Questions tagged [dfa]

Questions about deterministic finite automata

Filter by
Sorted by
Tagged with
1 vote
0 answers
41 views

Constructing a DFA with $n$ states for which $L*$ needs $n$ equivalence queries

I'm working on constructing deterministic finite automata (DFAs) with a specific learning complexity when using the L* algorithm developed by Dana Angluin. My goal is to create a DFA of size ( n ) ...
2 votes
1 answer
111 views

What is the current state of the art on exact identification of DFAs with a maximum N states

This is a question about the blackbox grammar inference of deterministic finite state automata (DFAs). In particular I want to ask about when one can exactly identify the target DFA using queries to ...
8 votes
3 answers
323 views

Relationship between size of Boolean functions and DFAs

Are there any works that study the relationship between Boolean functions and the size of the minimal DFAs required to represent those Boolean functions? Boolean functions refer to the usual ...
7 votes
1 answer
217 views

Counting the different subsets of nodes seen when iterating a subset through a directed graph

For a given directed graph $G = (V, E)$ (possibly with loops), and some $S\subseteq V$ define the operation $G(S) = \{ v\mid (u,v)\in E\text{ for some } u\in S \}$. Now consider the infinite sequence $...
6 votes
1 answer
490 views

Error in Robson's proof about separating strings?

One of my students discovered a possible mistake in Robson's classic paper Separating strings with small automata. The issue is in the proof of Theorem 1, giving the simpler bound $O(\sqrt{n\log n})$. ...
6 votes
0 answers
72 views

Updating (minimal) DFA incrementally

Is there algorithm to incrementally update (minimal) DFA? Namely, having relatively large minimized DFA I want to update it incrementally using union and sudtraction with other (relatively small, ...
5 votes
1 answer
301 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 vote
0 answers
123 views

Real life application of two-way DFA

I am currently studying two-way DFA and I couldn't find and research anything on its real-life applications if there are any. I am very unsure where it could be used and any ideas would be great. tyia
7 votes
1 answer
237 views

Is DFA language inclusion decidable in quasi-linear time? [duplicate]

Given two DFAs $A_1$ and $A_2$, we want to decide whether $\mathcal{L}(A_1) \subseteq \mathcal{L}(A_2)$. Of course, one can compute whether $\mathcal{L}(A_1) \cap \mathcal{L}(A_2) = \mathcal{L}(A_1)$. ...
6 votes
0 answers
126 views

What is the Simplest type of automaton that can simulate all DFAs?

During recent research in a somewhat unrelated field (Spin Physics), I stumbled across a subclass of regular languages. The context of the research poses the question what the minimal power of the ...
26 votes
4 answers
3k 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 ...
-6 votes
2 answers
113 views

I have to make a dfa over the alphabet Σ = { 0, 1, 2 } of strings that end with the same digit twice; e.g., strings that end in 00, 11, 22 [closed]

hi can you please go over my dfa for this and tell me if its correct??
7 votes
1 answer
207 views

Random Cerny Conjecture

For simplicity, all DFAs will be using the binary alphabet $\{0,1\}$. Let $M$ be a synchronizable DFA. We let $p(M,n)$ be the probability that a random $x\in \{0,1\}^n$ will synchronize $M$. We define ...
14 votes
1 answer
5k 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, ...
16 votes
2 answers
2k 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 ...
69 votes
10 answers
9k 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'...
18 votes
2 answers
505 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 ...
9 votes
2 answers
806 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 $...
10 votes
2 answers
482 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 ...
11 votes
2 answers
424 views

Bounds on this Strategy for Separating Words

Question Given binary string $z \in \{0,1\}^n$, let $f(z)$ be the smallest integer $k$ such that there exists a DFA with $k$ states, such that reading $z$ from a specific starting state, we end at a ...
6 votes
2 answers
2k views

2DFA to 1DFA - Converting two way deterministic finite automata to one way deterministic finite automata

How can I convert a 2DFA to a normal DFA. Is there an algorithm/elegant way to do that ? I've been researching this for a few days but I coundn't find anything. Actually I want to implement that in ...
6 votes
1 answer
233 views

Complexity of DFA intersection in this specific case?

In general, the size of the DFA that recognizes the intersection of $n$ languages is exponential in $n$. However, in my case I am computing the intersection of a very restricted subset of possible ...
8 votes
1 answer
223 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 ...
2 votes
1 answer
564 views

Oncina-Garcia RPNI algorithm for learning DFAs

The question refers to this paper: ftp://altea.dlsi.ua.es/people/oncina/articulos/asspr1992.pdf Given a sample of $p$ positive and $n$ negative strings, RPNI constructs a consistent DFA in time $O((p+...
6 votes
1 answer
191 views

Separating words and graph isomorphism

I wonder if there are any known implications of Babai's recent quasi-polynomial time algorithm for Graph Isomorphism to separating words by DFA's. In both cases the ultimate goal is to differentiate ...
3 votes
1 answer
236 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 ...
9 votes
0 answers
290 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 ...
-1 votes
1 answer
113 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,...
8 votes
1 answer
1k 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$ : ...
3 votes
1 answer
471 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
1 answer
80 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 ...
2 votes
0 answers
76 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-...
7 votes
1 answer
214 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 $...
25 votes
1 answer
1k 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 ...
6 votes
2 answers
215 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
2 answers
987 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
1 answer
5k 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 ...
261 votes
11 answers
100k 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 ...
5 votes
0 answers
202 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
5 answers
1k 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
2 answers
278 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
1 answer
262 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 $...
23 votes
1 answer
981 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 ...
1 vote
1 answer
1k 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
1 answer
148 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 ...
9 votes
1 answer
1k 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
1 answer
2k 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 ...
2 votes
0 answers
335 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. ...
7 votes
1 answer
268 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
1 answer
753 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 ...