# Tagged Questions

29 views

### What are the connections between P-complete and L-complete [on hold]

I have limited knowledge about complexity theory. From what I learned, DFA membership testing is an L-complete problem. However, I am not quite sure what it implies. For example, is it also a P-...
24 views

### Asking for DFA Problem Solution [closed]

Help me to find out the solution, Give a DFA for Σ = {a, b} that accepts strings with ( ab U aba )*
347 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, ...
66 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 ...
390 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 ...
203 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$....
197 views

838 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 ...
456 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 ...
261 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/...
391 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 ...