Questions tagged [automata-theory]

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

3
votes
5answers
761 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 ...
-2
votes
2answers
188 views

An algorithm that determines if regular language accepts all string of its alphabet [closed]

Let $L$ be a regular language with the alphabet $\Sigma$. I'm trying to find an algorithm to tell whether $L=\Sigma^{*}$, whether $L$ accepts all strings in its alphabet. I think this algorithm uses ...
6
votes
2answers
239 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 $...
9
votes
1answer
233 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 ...
-2
votes
1answer
210 views

Writing a regular expression for character set $\Sigma = \{a,b,(,)\}$ that not have a parenthesis inside a parenthesis [closed]

Let character set $\Sigma=\{a,b,(,)\}$. I want to write a regular expression for the language $L$ that does not have a parenthesis inside a parenthesis. For example, $(abaab)(bbbaa) \in L$, while $(...
6
votes
2answers
234 views

Deciding functionality of transducers over infinite words

Given a finite state transducer defining a rational relation over infinite words, it is known to be decidable whether or not the relation is a function, i.e. whether each infinite input word is ...
5
votes
0answers
93 views

Why do multi-stack visibly pushdown languages label each call/return with a particular stack?

In A Unifying Approach for Multistack Pushdown Automata, multistack visibly pushdown automata are defined in terms of an alphabet where each symbol is either a call or return for a particular stack or ...
6
votes
0answers
775 views

What would a PDA be with a queue instead of a stack?

A while ago it occurred to me that the stack data model in a push-down automaton could be exchanged for a queue or deque model. I've explored this a bit as a pet project and it looks like an automaton ...
3
votes
1answer
108 views

Deterministic Parity Automata require unbounded index

Deterministic parity automata $(Q, \Sigma, q_0, \Delta, c)$ are powerful enough to recognize all $\omega$-regular languages. However, the number of priorities they require for a language can become ...
15
votes
1answer
537 views

Are DPDAs without a $\epsilon$ moves as powerful as DPDAs with them?

In the formal description of Deterministic Pushdown Automata, they allow $\epsilon$ moves, where the machine can pop or push symbols onto the stack without reading a symbol from the input. If these $\...
2
votes
2answers
104 views

If the set of factors of an infinite word $\xi$ is regular, is this property stable under “shift's” of $\xi$?

Let $\xi$ be an infinite binary sequence, and denote by $T(\xi)$ the set of all factors (infixes) of $\xi$. Also if $w$ is some finite prefix of $\xi$, denote by $\xi/w$ the unique $\eta$ such that $w ...
10
votes
1answer
267 views

What is the state complexity of the copy language?

Let a number $n$ be given. Consider the following language $L_n = \{ \; ww \; \vert \; w \in \{0,1\}^{n} \; \}$. In words, $L_n$ is the set of copy strings of length $2n$. Consider the following ...
4
votes
1answer
1k views

Emptiness of PDA without constructing the corresponding CFG

The emptiness problem for Context free Grammars(CFG) is well studied. The same holds for the equivalence problem between Pushdown Automata (PDA) and CFGs. Therefore, given a PDA, the straightforward ...
9
votes
0answers
430 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 ...
5
votes
0answers
115 views

Learning Finite Automata Behavior by Experimentation

This conjecture is from an expert in Game Theory area, I post it here to draw more attentions of TCS experts. Discussions and comments are welcome. http://gtcenter.org/WCS_Call_for_papers.pdf An ...
6
votes
1answer
211 views

Who introduced nondeterministic M-automata, and proved that the finite ones recognize the rational sets over M?

Let $M$ be a monoid. The family $\operatorname{RAT}(M)$ of rational sets over $M$ is defined inductively: If $L$ is a finite subset of $M$, then $L\in\operatorname{RAT}(M)$. If $K,L\in\operatorname{...
4
votes
1answer
441 views

Decidability of membership in the fixed point of a rational relation

Given a finite alphabet $\Sigma$, a non-deterministic finite-state transducer representing rational a relation $T \subseteq \wp(\Sigma^* \times \Sigma^*)$, a finite state machine representing a ...
10
votes
2answers
182 views

Separating lists of words

There is an open problem in formal languages known as the Separating Problem; which is briefly stated as given two distinct strings of length $n$, how large of a DFA is required to "separate" them, ...
5
votes
1answer
138 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 ...
2
votes
0answers
193 views

Complexity of DBA-recognizable Omega-Languages

Given an $\omega$-regular expression $r$, how difficult is it to decide if $L(r)$ is recognizable by some deterministic Büchi automaton? I know it is solvable in EXPTIME by converting the regular ...
3
votes
1answer
105 views

Finite state transducer with infinitary outputs or without emphasis on acceptance?

1) Is there a notion of (deterministic) finite state transducer (FST) that allows the possibility of producing an infinite stream of output symbols? In other words, one where the transduction ...
23
votes
1answer
1k views

Deciding emptiness of intersection of regular languages in subquadratic time

Let $L_1,L_2$ be two regular languages given by NFAs $M_1,M_2$ as input. Assume we would like to check whether $L_1\cap L_2\neq \emptyset$. This can clearly be done by a quadratic algorithm which ...
3
votes
0answers
233 views

Equivalence of deterministic finite transducers over finite/infinite words

Equivalence of deterministic finite transducers - a special case of single-valued finite transducers - is decidable because it is decidable whether a transducer is single-valued. Note that two ...
23
votes
1answer
775 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 ...
3
votes
2answers
244 views

computing maximal bit density over a FSM

let $L$ be a regular language defined by a FSM over binary symbols $\{0,1\}$. consider a function $f(x)$ on words/ strings that computes "bit density", defined as the number of $1$'s in a word ("...
9
votes
1answer
707 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 ...
10
votes
2answers
344 views

Minimizing Automata accepting $\omega$-words (i.e. infinite words)

What is the standard approach on minimizing Büchi-Automata (or also Müller-Automata)? Transfering the usual technique from finite words, i.e. setting two states to be equal if the words "running out" ...
7
votes
1answer
110 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 ...
1
vote
1answer
226 views

Alternating tree automata for arbitrary arity tree

Could alternating tree automata be used for recognizing set (language) of arbitrary-arity trees? More specifically, as an example: let $\Sigma = \{a,b,c\}$ - labels for tree nodes. Trees from $T$ ...
12
votes
2answers
280 views

Pseudorandom generator for finite automata

Let $d$ be a constant. How can we provably construct a pseudorandom generator that fools $d$-state finite automata? Here, a $d$-state finite automata has $d$ nodes, a start node, a set of nodes ...
5
votes
1answer
823 views

What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction?

What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction? Why? Details: http://en.wikipedia.org/wiki/Powerset_construction states that the worst-...
5
votes
1answer
788 views

Closure properties of deterministic context-sensitive languages

There does seem to be a lot of information regarding the closure properties of both deterministic context-free and nondeterministic context-sensitive languages. However, the literature is almost mute ...
5
votes
2answers
154 views

Can real-time deterministic multicounter automata recognize the marked palindrome language?

Consider the marked palindrome language which is defined as MPAL=$\{ w\#w^r | w \in \{a,b\}^* \}$. It is easy to recognize MPAL using only a single stack. My question is whether MPAL can be ...
-1
votes
1answer
999 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 ...
10
votes
2answers
639 views

Are regular languages closed under addition?

Specifically what I mean by addition is, we define $\Sigma_i$ to be the alphabet $\{0, 1, 2, ..., i\}$. Given regular languages $A$ and $B$ under some alphabet $\Sigma_i$, look at $A\times B$. For ...
3
votes
2answers
233 views

Automata and a kind of pumping lemma on state transition function

We encountered this question as an exercise in a Büchi automata book a couple of decades ago, and back then gave a few tries thinking that it should be easy. But haven't seen a solution. My ...
14
votes
2answers
480 views

Does XOR automata (NXA) for finite languages benefit from cycles?

A non-deterministic Xor automata (NXA) is syntactically an NFA, but a word is said to be accepted by NXA if it has an odd number of accepting paths (instead of at least one accepting path in the NFA ...
5
votes
1answer
384 views

What is the importance of linear languages?

What is the point of linear languages? They appear to be an intermediate set of languages in between regular and context-free languages, but do they have any useful or nice properties that either have ...
3
votes
0answers
142 views

Restricted-Input Automaton

In the classic setting, an automaton for a language $L$ is required to accept all words in $L$ and reject/get stuck on every word in $\Sigma^*\setminus L$. All of the related concepts are then ...
11
votes
0answers
292 views

Can we approximate the number of words accepted by an NFA?

Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. In a related question, it was suggested that exact counting of the number of words accepted by $M$ is $\#P$-Complete. The second ...
1
vote
1answer
136 views

Example of a $U^\omega$ that is not Deterministic Büchi recognizable

Is there a regular language $U$, for which $U^\omega$ is not a Deterministic Büchi recognizable language. I have been thinking over it for some time, but have been unable to come up with an example.
0
votes
2answers
121 views

finite automata under morphism [closed]

Given two (deterministic) finite automata $A, B$ over $\Sigma$, a mapping $h:\Sigma\rightarrow \Sigma'$ Naturally $h$ can be extended to a mapping in $\Sigma^*\rightarrow \Sigma'^*$ which is denoted ...
5
votes
1answer
164 views

What language $L \in NCM$ has $\overline{L} \not \in NCM$?

$NCM$, the class of non-deterministic reversal-bounded counter machines, has a lot of interesting dependability and closure properties. It's known that, unlike the deterministic version, NCM is not ...
4
votes
1answer
247 views

What characterizations exist for the grammars that can express subsets of the context-free languages?

It is well known that CFGs and PDAs are equivalent, and there has been extensive research about the relationship between deterministic pushdowns and $LR(1)$ grammars, as $DCFL$ is a subset of $LR(1)$. ...
6
votes
2answers
152 views

Are deterministic context-free languages closed under outfix (or other erasing operations)

Define the outfix of a language $L$ to be $Outf(L) = \{xy \mid \exists z. xzy \in L \}$. Are any known results about whether deterministic context-free languages are closed under this operation, or ...
18
votes
5answers
579 views

What notable automaton models have polynomially-decidable containment?

I'm trying to solve a particular problem, and I thought I might be able to solve it using automata theory. I'm wondering, what models of automata have containment decidable in polynomial time? i.e. if ...
16
votes
1answer
404 views

Can constant ambiguity reduce the state complexity of a regular languages?

We say that NFA $M$ is Constantly Ambiguous if there exist $k\in \mathbb{N}$ such that any word $w\in \Sigma^*$ is accepted by either $0$ or (exactly) $k$ paths. If automaton $M$ is constantly ...
-1
votes
2answers
120 views

Looking for menu-driven coding editor based on a programming language state machine [closed]

I'd like to know whether an application development environment exists that uses a menu-driven coding editor that employs a programming language state machine. This would mean that commands, variable ...
1
vote
0answers
85 views

Which paper first showed that any context-free grammar (CFG) is equivalent to some CFG in Chomsky normal form?

Which paper first showed that any context-free grammar (CFG) is equivalent to some CFG in Chomsky normal form? I cannot find an reference.