All Questions
Tagged with finite-automata reference-request
23 questions
2
votes
1
answer
28
views
Complexity of deciding if a DFA is counter-free
It is well-known that deciding whether an NFA or a regular expression define a counter-free/star-free language is PSPACE-complete.
Does the problem become easier if I have a DFA as input? What's the ...
- 548
4
votes
1
answer
148
views
Building the minimal automaton from the syntactic monoid of a language
I'm studying the algebraic view of automata theory. One of the basic results is that the syntactic monoid of a language $L$ is the transition monoid $M(A)$ of the minimal automaton $A(L)$ accepting $L$...
- 548
2
votes
0
answers
39
views
Why are VFSMs not more commonly used?
For a job several years ago I worked with a team using technologies built around Virtual Finite State Machine models for system fault analysis and remediation. Since then, I've found it to be a ...
- 121
1
vote
1
answer
42
views
In which reference can I find a definition for the equivalence of DFAs?
How is the equivalence of DFA defined? I found the equivalence of states --- James Hein, section 5.3, page 301. But he doesn't define equivalence between entire automata. (Ullman and Hopcropft seem ...
- 237
1
vote
1
answer
72
views
Simple property of DFAs
Do you know if this simple property of a DFA is stated as a property (or theorem) in some Automata theory book (possibly with a particular name)?
Property: Given a DFA $A = \{ Q, \Sigma, \delta, q_0, ...
- 12.7k
2
votes
0
answers
84
views
Minimization of simple cyclic automata
Version 1 of the question: I am looking for any correct $O(n)$ algorithm in the literature which will solve the DFA minimization problem referred to in the quote below from [Almeida & Zeitoun 2008]...
- 947
2
votes
0
answers
236
views
State of the Art in linear-time DFA 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 ...
- 947
6
votes
2
answers
457
views
How similar are two DFAs? -not just binary equivalence-
Are there any measures to compute similarity (or distance) between two DFAs?
If yes, which are the main references?
I need a measure of similarity, not only a (binary) equivalence test.
"Similarity"...
- 165
5
votes
1
answer
755
views
space complexity of DFA intersection problem
the DFA-intersection computation problem, given two DFAs specified on the input, compute the intersection DFA, or the decision problem to determine its emptiness, turns out to have wider/ deeper ...
- 11.1k
11
votes
3
answers
2k
views
Algorithms for minimizing Moore automata
Brzozowski's algorithm can be extended to Moore automata but its time complexity is exponential in general. Is there any other algorithm for minimization of Moore automata? What are the running times ...
- 111
6
votes
1
answer
388
views
Who invented the state elimination algorithm for converting finite automata into regular expressions?
The state elimination algorithm is an algorithm for converting finite automata into regular expressions. It's found in many textbooks, including Sipser's Introduction to the Theory of Computation. ...
- 9,222
0
votes
1
answer
84
views
LL(k) Prediction Techniques (and Insight on method applied)
I'm requesting references for LL(k) in situations where k > 1 for reasons described below.
I'm looking for research/notes/...
5
votes
0
answers
94
views
Languages recognized by finite state automata of polynomially growing size
In the course of my research (condensed matter physics stuff), I stumbled over the following concept:
The class of regular languages can be defined via finite state machines (FSM):
A language $L$ is ...
- 91
10
votes
2
answers
296
views
Method for measuring the 'similarity' between FSA grammars?
I'm working with a pattern matching algorithm that generates an acyclic finite state automaton that accepts a given text string and all its substrings. The FSA algorithm is being run on a symbolic ...
- 109
11
votes
2
answers
742
views
Is the reversal of a minimal DFA also minimal?
The question is pretty much in the title. Is there ever a time where some language $L$ can be accepted by a minimal DFA with $n$ states, but $L^R$, the reversal of $L$, can be accepted by a DFA with $...
- 30.1k
2
votes
3
answers
1k
views
Does there exist a proof of closure of regular languages under regular substitution by giving the corresponding DFA?
Every proof I can find of this result is by way of regular expressions. Is there any "constructive" proof that defines the corresponding DFA (probably NFA)? For instance the proof of concatenation ...
- 630
5
votes
2
answers
143
views
What is Finite Automata Bowl?
I was trying to find info about this Finite Automata type FAB (Finite Automata Bowl) and wasn't able to find a lot. It is basically the rules that apply to PDA apply to FAB except you drop the ...
- 51
4
votes
1
answer
368
views
C(++) library for DFAs - free for academic use
(I'm aware that software questions are better suited for stackoverflow, but since DFAs are not something that software developers usually care about, I hope it's alright if I ask here.)
I'm currently ...
- 2,019
2
votes
1
answer
222
views
Mealy machines to model ciphers [closed]
Similar questions have occurred quite a number of times (1) (2) (3), but I have, say, a specific instance of one. I'm aware of a bunch of applications of finite automata, but would you provide an ...
- 181
7
votes
1
answer
180
views
Results on the languages recognized by undirected DFAs
For my Bachelor's thesis, I consider the class of languages recognized by symmetrical DFAs, that is, deterministic (complete) finite automata satisfying the following condition:
Let $A$ be a ...
- 1,291
13
votes
2
answers
2k
views
What is the complexity of the emptiness problem for 2-way DFAs?
I'm wondering, what is the time-complexity of determining emptiness for 2-way DFAs? That is, finite automata which can move backwards on their read-only input tape.
According to Wikipedia, they are ...
- 30.1k
11
votes
1
answer
1k
views
Difference between the languages accepted by two DFAs with different initial state/accepting states?
Recently, I asked a question on Math SE. No response yet. This question is related to that question, but more technical details toward computer science.
Given two DFAs $A = (Q, \Sigma, \delta, q_1, ...
- 440
8
votes
6
answers
13k
views
Practical application of Finite State Machines
I am looking for practical applications of Finite State Machines like DFA, NFA, Moore, Mealy machines...
It would be helpful if someone point to examples from Linux Kernel. I know that DFA is used in ...
- 2,221