Questions tagged [automata-theory]

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

Filter by
Sorted by
Tagged with
7
votes
1answer
1k views

Photo of «Introduction to automata…» by Hopcroft and Ullman '79 cover?

Where can I get the photo of “Introduction to automata theory, languages and computation” by Hopcroft and Ullman '79 (first edition) cover in order to be able to read all the phrases placed on the ...
3
votes
0answers
305 views

Name this digraph

I am trying to track down the name of this digraph and some references: You take all members of the transformation semigroup on $n$ elements, $T_{n}$. For two members $x$ ,$y$ ; if $x$ is in the ...
2
votes
0answers
776 views

What is the relationship between the number of states in Quantum Finite Automata and the number of non-regular languages they can recognize?

It is has been shown that Quantum Finite Automata can recognize at least some non-regular languages. What is the relationship between the number of states in a qfa and the number of non-regular ...
8
votes
1answer
340 views

Measurable language which is not $\omega$-regular

Let $\Sigma$ be a finite alphabet and let $\Sigma^\omega$ be the set of all infinite words over $\Sigma$. Consider $$ d(x,y):=2^{-\min(n \in \Bbb N_0:x_n\neq y_n)} $$ to be the metric on $\Sigma^\...
9
votes
2answers
389 views

Are there families of formal languages known to be truly PAC learnable?

I specifically mean language families that admit arbitrarily long strings -- not conjunctions over n bits or decision lists or any other "simple" language contained in {0,1}^n. I am asking about "...
4
votes
2answers
890 views

Finite state transducer that sorts

Is it possible to sort a string of arbitrary length with a finite-state transducer? How big would this transducer be (the smaller the better)? (I'm not a computer scientist, so less technical answers ...
7
votes
0answers
150 views

Size complexity of probabilistic two-way automata for a Boolean function

I'm interested in computing Boolean functions $f:\{0,1\}^n\rightarrow\{0,1\}$ with two-way finite automata and I will measure the complexity of a Boolean function by the number of states for the ...
1
vote
2answers
339 views

Find minimum number of transformations to transform from input to target string

Given that I have an input string, for example: aab And I am given a target string, for example: bababa And then I am given a ...
-1
votes
0answers
117 views
0
votes
1answer
158 views

Implicit Non-deterministic Buchi determinization

I am doing implicit Buchi determination for LTL logic in hardware where the combinational logic represents the set of states. But instead of using acceptance states, I am using final state (as in ...
1
vote
1answer
406 views

How to show that ECTL* is more expressive than CTL* $\cup$ Büchi (with an example)

I am looking for a preferably simple property that is expressible in ECTL* but not in CTL* and not in Büchi, with a citable reference to the proof. Details of what I've tried: I've tried a ...
4
votes
1answer
422 views

Probabilistic circuit complexity or size of probabilistic 2-way automata for Boolean functions

If we consider circuits with arbitrary binary logic gates one can prove by a counting argument that there exists a Boolean function on $n$ variables that require a circuit of size $ \Theta \left( 2^n/...
2
votes
2answers
235 views

Alternating automata

In the paper Fast LTL to Buchi Automata Translation (2001, Gastin and Oddoux) the authors, while defining co-Buchi alternating automata define $\Sigma’= 2^\Sigma$ where $\Sigma$ is the alphabet. ...
12
votes
2answers
730 views

Expressiveness of Büchi vs CTL(*)

What is the relationship between the expressiveness of LTL, Büchi/QPTL, CTL and CTL*? Can you give some references that cover as many of these temporal logics as possible (especially between linear- ...
4
votes
2answers
319 views

Inductive definition of ECTL*: how are recursive formulas forbidden?

In [1], the extended computation tree logic ECTL* is inductively defined as the propositional formulas over all E($A(F_1,..F_n)$), where E is the existential path quantifier and $A$ some Büchi ...
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 ...
12
votes
1answer
717 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, ...
0
votes
2answers
172 views

iterations of a $\epsilon$-FSM transducer on a tape as equivalent to a TM computation

A question partly inspired by a recent question[1] on the utility of FSMs: Years ago noticed the following property of FSM transducers with $\epsilon$-transitions (which allow an "empty" transition ...
12
votes
2answers
434 views

Why is the state of a FSM traditionally denoted $q$?

While teaching how to implement FSMs using synchronous logical circuits, I noticed an intriguing coincidence: in both the theoretical CS world, and in the electrical engineering world, "state" is ...
5
votes
2answers
2k views

Why were Finite Automata and Turing Machines created?

It seems the creation of Turing Machines and finite automata were apart by at least 2+ decades. That is TMs don't really reference FAs for their working and vice versa; TMs and FAs were developed ...
9
votes
0answers
145 views

A language outside the Boolean closure of stochastic languages

Stochastic languages, that is, those accepted by probabilistic automata, are known to not be closed under intersection, union, concatenation, and morphism, even on unary languages. I have two ...
24
votes
1answer
480 views

complexity of the half language

For any language $L$ over $\Sigma^*$, define $$L_{1/2} = \{x \in \Sigma^* : xy\in L, y\in\Sigma^{|x|} \}.$$ In words, $L_{1/2}$ consists of all $x$ for which there is a $y$ of equal length such that $...
1
vote
0answers
190 views

Dynamic k-shortest paths in a weighted transducer

I'm looking for references relating to dynamically computing the k-shortest output paths through a stochastic, acyclic, weighted transducer that is being constructed on-the-fly. In this scenario ...
19
votes
3answers
1k views

Is the concept of the Turing Machine derived from automata?

I was just recently having a discussion about Turing Machines when I was asked, "Is the Turing Machine derived from automata, or is it the other way around"? I didn't know the answer of course, but I'...
1
vote
0answers
90 views

Automatic structures/functions: Is (Z,+) under a unary representation automatic?

The group $(\mathbb{Z}, +)$ is automatic (ala Khoussainov) when using the "standard" representation in a decimal base. But if I want to use a different representation of Z, encoding my integers with ...
4
votes
1answer
214 views

State transducers for generating permutations

Let a finite alphabet $\Sigma$. Let $\mathcal{Reord_\Sigma}$ be the family of computable partial functions between the strings of this alphabet $r\,:\, \Sigma^*\, \rightarrow \Sigma^*$ with the ...
-3
votes
1answer
708 views

Minimal Turing Machine implementation / Von Neumann UC [closed]

I've written a small python program which implements a Turing Machine with a finite tape. It has a tape, a head, a state register and a set of transfer functions ("the program"). The difference to a ...
0
votes
0answers
77 views

Generalizing a set of positive and negative examples through DFAs [duplicate]

Possible Duplicate: Is finding the minimum regular expression an NP-complete problem? Let $\Sigma$ be an alphabet. Let $P$ and $N$ (the set of positive and negative examples) be two disjoint ...
4
votes
1answer
175 views

Getting an automaton from set of words in and out of a language [duplicate]

Possible Duplicate: Is finding the minimum regular expression an NP-complete problem? Let's suppose that I have an unknown language $\mathcal L$, I know only two (particularly large) sets of ...
7
votes
0answers
333 views

Examples of non-CSLs not created through diagonalization

Hopcroft & Ullman 1979, Intro to Automata Theory, Languages, & Computation states (p. 224) that "almost any language one can think of is CSL; the only known proofs that certain languages are ...
6
votes
0answers
273 views

Language of stack configurations of a pushdown automaton

Consider a pushdown automaton $A$ with stack alphabet $\Gamma$. Let $L$ be the language on $\Gamma$ of the stack configurations encountered during accepting runs of $A$. Is $L$ a context-free language?...
20
votes
5answers
2k views

A special class of languages: “circular” languages. Is it known?

Define the following class of "circular" languages over a finite alphabet Sigma. Actually, the name already exists to denote a different thing it seems, used in the field of DNA computing. AFAICT, ...
10
votes
0answers
258 views

A super-linear time problem in NL

It is a well-known fact that $ \mathsf{NL} = \cup_{k>0} \mathsf{2NFA[k]} $, where $ \mathsf{2NFA[k]} $ is the class of languages recognized by two-way nondeterministic finite automata with $ k>0 ...
12
votes
3answers
459 views

Minimal DFA satisfying a finite view of a language

Say one has a language $L \subseteq \Sigma^*$, but one doesn't know what strings are actually part of the language. All one has is a finite view of the language: a finite set of strings $A \subseteq L$...
3
votes
1answer
201 views

Automatically creating weighted DFAs penalizing sequences of subsets of the alphabet

For a given finite alphabet $\Sigma$, my goal is to write an algorithm that receives as input a sequence $V=V_{1}V_{2}\dots V_{n}$ of subsets ($V_{i}\subseteq\Sigma$), and returns a weighted ...
14
votes
0answers
206 views

The best known upper bound for two-way probabilistic finite automata with one-counter

It is known that the class of languages recognized by two-way deterministic finite automata with one-counter (2D1CAs) is a proper subset of $ \mathsf{L} $ (deterministic log-space): A 2D1CA can run at ...
4
votes
0answers
230 views

Intersection between register automata and pushdown automata over infinite alphabet

I'm not an expert in automata theory, this is a reference request. As far as I have understood it is known in the automata comunity that register automata by Kaminski are closed by intersection with ...
8
votes
3answers
771 views

1-way Quantum Finite Automata Example Question

I'm attempting to clarify my understanding in the example presented in Section 2.2 of 1-way Quantum Finite Automata: Strengths Weaknesses and Generalizations (this alternative link may also be useful)....
2
votes
0answers
206 views

Fast weighted intersection algorithm for CFG and FSA with self loops but no other circles?

We all know that arbitrary CFG and FSA can be intersected using the Bar-Hillel Construction, whose time complexity is unfortunately too expensive. On the other hand, there are efficient algorithms ...
11
votes
3answers
2k views

How to prove that a formula can not be expressed in LTL, but can be in Buchi automata?

I am looking for a general technique which can help me to prove not just that Buchi automata is more expressive model than LTL, but that the specific formula can/can't be expressed in LTL. For ...
-1
votes
1answer
84 views

Issue in understanding conditional likelihood for a producton rule

The Equation1 in paper in link explains how to assign probability to a production rule. Fig1 explains with an example. Now, I have a problem in understanding how to work with this formula since it ...
-5
votes
1answer
2k views

Proof that DFA that accepts string has NFA that accepts reversal of string

I have seen descriptions for an algorithm that can take a regular deterministic finite automata and create a non-deterministic finite automata that is guaranteed to generate the reverse of string ...
6
votes
2answers
352 views

Automata model with undecidable (or non-context-sensitive) languages and no $\varepsilon$-transitions.

Adding extensions to automata has always been a fruitful domain. But usually, one wants to add weak capabilities, as undecidability comes quickly into the picture. Take FSM with added stacks. It is ...
1
vote
0answers
143 views

Density of black cells in rule 110 cellular automata [closed]

Is there a way to compute the limit of the ratio (number of black cells)/(number of white cells), in the rule 110 or rule 30 automaton? With initial state = 1 black cell. Simulation of first 120000 ...
2
votes
1answer
490 views

Three questions about finite state machines

Suppose a finite state machine, FSM, has a fixed set of states $S$ and input/output channels $C$, and is uniquely specified by the fixed map $m : S\times D \to S\times D\cup {0}$. If a state $(c_i,s_j)...
7
votes
2answers
288 views

Smallest representatives of a quotient by an equivalence relation

Background Let $\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$ be a minimal DFA for a regular language $L$ such that $|Q|=n$, and let $\equiv_L$ be the relation given by $$x\equiv_Ly\text{ iff for all $u$: }xu\...
28
votes
2answers
2k views

How many DFAs accept two given strings?

Fix an integer $n$ and alphabet $\Sigma=\{0,1\}$. Define $DFA(n)$ to be the collection of all finite-state automata on $n$ states with starting state 1. We are considering all DFAs (not just connected,...
7
votes
2answers
699 views

Maximal munch rule issue for lexers: is detection decidable?

Edit: I realise that one of my problems is that I don't have a clear definition of my problem, which makes the question of whether it is detectable hard to answer. I'm therefore already happy with ...
12
votes
3answers
698 views

A “simple” language outside $CFL \cup coCFL$?

I am looking for a language L with the following properties: L should not be context-free. L's complement should not be context-free. (Everything you see in textbooks as prime examples of non-context-...