Questions tagged [automata-theory]

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

Filter by
Sorted by
Tagged with
4
votes
1answer
254 views

Is it known if $CFL \subseteq NSPACE(o(log^2(n)))$?

$CFL$ is the class of context-free languages. Question Is $CFL$ known to be solvable in $o(log^{2}(n))$ non-deterministic space? What about $DCFL$?
-1
votes
1answer
91 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,...
13
votes
1answer
698 views

Complexity of the problem of words with fewest distinct letters accepted by a finite automaton

Given a finite (deterministic or nondeterministic, I don't think this has much importance) automaton A and a threshold n, does A accept a word containing at most n distinct letters? (By k different ...
12
votes
1answer
137 views

Regular language that discriminates between two deterministic CFGs

Suppose you are given two deterministic push down automata which recognize languages $A$ and $B$, and wish to determine whether there is a regular language $R$ such that $A \subseteq R$ and $R \cap B =...
16
votes
1answer
388 views

Are there variants of visibly pushdown automata that allow pushing of words onto the stack?

I'm wondering, are there any papers or research dealing with visibly pushdown automata, but allowing words, rather than single letters, to be pushed onto the stack. Alternately, a construction which ...
41
votes
10answers
15k views

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

Real computers have limited memory and only a finite number of states. So they are essentially finite automata. Why do theoretical computer scientists use the Turing machines (and other equivalent ...
7
votes
1answer
133 views

Random Deterministic Automata

I am familiar with the term of random graphs, such as $G(n,p)$- a distribution over simple undirected graphs with $n$ vertices, where each edge appears in a graph w.p. $p$. That is, each graph $G=(V,E)...
9
votes
2answers
263 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 ...
1
vote
1answer
104 views

Set of languages that can represent every c. e. languange

Could we find any set of languages $S$, such that it can represent every c. e. languange as it's union, intersection, complement, production(times of element ), and $S\subset X$, where $X\subseteq c.e....
3
votes
1answer
65 views

Can any c.e. language with infinite words be decomposed into infinite CFLs with infinite words?

Suppose $L$ is a computably enumerable language, can it be decompose into infinite CFLs with infinite words ? $$L=\bigcup_{L_i\in CFL }^{\infty}L_i$$ Second question: if it is possible that every $L$...
-1
votes
1answer
74 views

Is there an inherently ambiguous language which can not be recognized by Deterministic LBA?

Is there inherently ambiguous language which can not be recognized by Deterministic LBA? For example, $L=\{wv: w,v=(x|y)^*, w=w^R,v=v^R\}$, is there any deterministc LBA that recognizes $L$ ?
1
vote
0answers
457 views

Equality Constraints over Sets with Tree Automata

Tree Automata can be used to model sets of values of a Herbrand Universe, for example, to model possible values in a functional program. Systems of subtype constraints over set expressions have ...
4
votes
1answer
1k views

Is Hartmanis-Stearns conjecture settled by this article?

The paper "On the computational complexity of algebraic numbers: the Hartmanis--Stearns problem revisited" by Boris Adamczewski, Julien Cassaigne, Marion Le Gonidec https://arxiv.org/abs/1601....
5
votes
1answer
186 views

What is the motivation behind defining Deterministic Looping Automata?

I was wondering about what could possibly be the motivation behind defining the deterministic looping automata? What puzzles me is that they accept a word iff they have a run on it! I believe they ...
8
votes
1answer
517 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$ : ...
2
votes
1answer
215 views

Deformation of finite regular languages [closed]

Let $L \subseteq \{0,1\}^n$ be any finite regular language s.t it has an acyclic DFA. Let $C$ be some class of acyclic DFAs. Let $\sigma \in S_n$ be a permutation on $n$ symbols. We can apply $\...
9
votes
1answer
194 views

Automata recognizing $X^*$ for a finite code $X$

Let $\Sigma$ be a finite alphabet. A code $X$ over $\Sigma$ is a subset of $\Sigma^*$ such that each word in $X^*$ can be uniquely represented as a concatenation of words in $X$. A code $X$ is finite ...
9
votes
3answers
262 views

Class of languages recognizable by single-tape 3-state TMs

I have for a while been curious about Turing Machines with exactly one tape and exactly 3 states (namely the start state $q_0$, the accept state $q_{accept}$, and the reject state $q_{reject}$). Note ...
1
vote
0answers
78 views

Relation between MDPs and non-deterministic finite automatons

I'm confused as to the relation (computability-wise) between markov decision processes and NFAs. Are finite state MDPs expressible as regular grammars? If so, are markov decision processes thus ...
1
vote
0answers
100 views

Convenient forms of Turing machines

Let us suppose that I have defined a new convenient form of the Turing machine for processing of some specific sort of commonly used structures. This form of TM contains some specific features ...
6
votes
1answer
423 views

Pumping Lemma over 2 way Automaton

Pumping Lemma essentially implies that for a NFA $N$ having $N_0$ states over a unary language $L_0$ any string belonging to $L_0$ can be obtained by 'pumping' one of the strings that have a length ...
6
votes
1answer
223 views

Has there been a study of circuits operating on arrays?

Much ink has been spilled studying the theory surrounding computation by combinatorial circuits operating on bits or boolean values - with AND, OR and NOT gates (as those are enough to implement any ...
19
votes
2answers
1k views

Status of Cerny Conjecture?

A DFA has a synchronizing word if there is a string that sends any state of the DFA to a single state. In ‘The Cerny Conjecture for Aperiodic Automata” by A. N. Trahtman (Discrete Mathematics and ...
9
votes
1answer
236 views

Transition monoid membership for DFAs

Given a complete DFA $A=(Q, \Gamma, \delta, F)$, we can define a collection of functions $f_a$ for each $a\in \Gamma$and with $f_a:Q\rightarrow Q$, $f_a(q)=\delta(q, a)$. We can generalize this notion ...
2
votes
1answer
80 views

Giving a finite collection of infinite words “complex” enough with respect to automata measure

We consider acceptance by Büchi automata. Let $X = \{0,1\}$ and $X^{\mathbb N}$ the set of all infinite sequences. Then for each $n$ do we have a finite collection $\{ \xi_1, \xi_2, \ldots, \xi_k \}$ ...
7
votes
1answer
170 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 $...
0
votes
0answers
149 views

Questions about the definition of the Quantum Turing Machine

I am trying to have a better understanding of the definition of the Quantum Turing Machine. My questions: If the output of a quantum program is the eigenvalue of the ground state of a Hamiltonian ...
16
votes
1answer
906 views

Quadratic relationship between nondeterministic and deterministic space?

Savitch's theorem shows that $\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)$ for all large enough functions $f$, and proving that this is tight has been an open problem for decades. Suppose ...
23
votes
1answer
786 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
2answers
464 views

In the context of regular languages, must the alphabet be finite?

In The Theory of Parsing, Translation, and Compiling, Volume I, Section 0.2.1 (p.15 / 1972), Aho and Ullman casually write that "[a]n alphabet need not be finite or even countable, but for all ...
7
votes
1answer
399 views

Shortest string in the intersection of a context-free language and a regular language

For a language $X$, define $ss(X) = \min_{x\in X} |x|$, the length of the shortest string in $X$. For simplicity, we define $ss(\emptyset)=0$. Let $L$ be a context-free language generated by a context-...
2
votes
1answer
77 views

CFGs in a certain normal form

Consider Context-Free Grammars with rules of the form $S\to\epsilon$ or $A\to aB | Ba|a$, meaning that any nonterminal other than $S$ can be replaced by a terminal, or by a pair of letters exactly one ...
12
votes
1answer
427 views

Minimizing residual finite state automata

Residual finite state automata (RFSAs, defined in [DLT02]) are NFAs that have some nice features in common with DFAs. In particular, there is always a canonical minimum sized RFSA for every regular ...
5
votes
0answers
140 views

Mastery-based grading for Theory of Computation

I would be interested to learn of anyone's experience using mastery-based (or "mastery-level") grading in a Theory of Computation course. Usually this requires—at a minimum— a detailed ...
3
votes
0answers
231 views

Providence of pumping lemmas for regular languages

I'm looking to track down who discovered the following pumping lemmas for regular languages. (where $p$ is the pumping constant.) Reg($L) \rightarrow \exists p\forall w(\in L) \forall u_1u_2v(\in \...
2
votes
1answer
235 views

Partition refinement in transition state systems (bisimulation contraction)

I am trying to understand bisimulation contraction of Kripke models. I have read these lecture slides and this Wikipedia page, but I still don't fully understand it. I can understand that the two ...
7
votes
1answer
285 views

Is this a regular relation?

I'm a linguist (and not a computer scientist!) investigating a new sort of linguistic formalism for mapping phonological strings into other strings - and I'm wondering if it's a regular relation that ...
3
votes
2answers
155 views

A property of suffix-free regular languages of maximal state complexity for the reverse operation

Let $L$ be a regular suffix-free language whose complete minimal automaton has $n$ states and that the minimal automaton of $L^R$ has exactly $2^{n-2}+1$ states. Let $p, q$ be two distinct states of ...
17
votes
2answers
240 views

A reference for a “more algebraic” approach to pushdown automata and CFLs?

In the Sakarovitch's book on automata theory, it is written in the introduction to the section on rationals in the free group that the material presented therein lays "the foundation of a truly ...
1
vote
0answers
165 views

Hysteresis in finite automata

The concept of hysteresis seems well suited to describe and distinguish finite automata: "Hysteresis is the dependence of the state of a system on its history." (Wikipedia, Hysteresis) "[The ...
6
votes
2answers
174 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 ...
14
votes
4answers
493 views

Hierarchies in regular languages

Is there any known "nice" hierarchy $L_0 \subseteq L_1 \subseteq L_2 \subseteq \dots$ (may be finite) inside the class of regular languages $L$? By nice here, the classes in each hierarchy capture ...
3
votes
0answers
168 views

Formal definition of Turing Completeness [closed]

Wikipedia states: In computability theory, a system of data-manipulation rules […] is said to be Turing complete or computationally universal if it can be used to simulate any single-taped Turing ...
12
votes
2answers
505 views

Non-isomorphic minimal non-deterministic finite automata

Can somebody provide an example of two equivalent (recognizing the same language) minimal non-deterministic automata (NFA) which are not isomorphic?
3
votes
1answer
74 views

Size bound on Büchi automaton for complement

For a given Büchi automaton $\mathcal A = (A, Q, \delta, q_0, F)$ we define a congruence on $A^{\ast}$ by $$ \begin{array}{llll} u \sim_{\mathcal A} v & :\Leftrightarrow & \mbox{for all }s,s' ...
2
votes
1answer
51 views

Determining the Class of a given Cellular Automata structure

Is it possible to write an algorithm that can determine the class of a given cellular automata structure ? (ie. Wolfram's 4 Classes) Thank you Ricky
2
votes
2answers
217 views

Simplest Machine Model for a langauge $ L = \{(w\# )^{k}\;|\; w\in \Sigma^{*},\;k\in \mathbb{N}\}$

What is the simplest machine model accepting the following language? $$ L = \{(w\# )^{k}\;|\; w\in \Sigma^{*},\;k\in \mathbb{N}\}$$ In other words, $L$ is obtained by taking each string $w$ in $\...
11
votes
3answers
470 views

Are there non-constructive proofs of existence of “small” Turing machines / NFAs?

After reading a related question, about non-constructive existence proofs of algorithms, I was wondering if there are methods of showing existence of "small" (say, state-wise) computation machines ...
1
vote
0answers
99 views

Why is an automaton on finite words co-deterministic iff its transitions are co-deterministic

In the article Automata and semigroups recognizing infinite words an automaton is specified by $\mathcal A = (Q, A, E, I, F)$ where $I$ is a set of initial states and $F$ a set of final states, $Q$ ...
2
votes
0answers
77 views

Proof of the equivalence of Muller automata and Parity (or Rabin chain) automata

Let $A$ be some finite alphabet and $\mathcal A = (Q, \delta, q_0)$ be some determinisitic finite automaton. Then $\mathcal A$ accepts infinite words $\xi \in A^{\omega}$ according to the Muller ...