Questions tagged [automata-theory]

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

Filter by
Sorted by
Tagged with
3
votes
1answer
199 views

“Combining” two mealy machines [closed]

How could you combine two mealy machines, the first one $M_1$ has as input $\sum_{1}^*$ and as output $\sum_{2}^*$, the second machine $M_2$ uses the output $\sum_{2}^*$ as the input and outputs $\...
3
votes
3answers
115 views

Example of monoid $M$ such that $\operatorname{RAT}(M) \not\subseteq \operatorname{REC}(M)$

Let $M$ be a monoid, the family of rational sets $\operatorname{RAT}(M)$ is defined as the smallest set containing the finite subsets, and closed under union, concatentaion and the star operation. The ...
9
votes
1answer
159 views

Generalisation of the statement that a monoid recognizes language iff syntactic monoid divides monoid

Let $A$ be a finite alphabet. For a given language $L \subseteq A^{\ast}$ the syntactic monoid $M(L)$ is a well-known notion in formal language theory. Furthermore, a monoid $M$ recognizes a language $...
-4
votes
1answer
70 views

Prove that L* is a regular language [closed]

Suppose that L is any language , not necessarily regular, whose alphabet is {0}; that is the strings of L consist of 0's only. Prove that L* is regular.
7
votes
2answers
176 views

Closure of Recognizable Languages under Kleene Star: Algebraic Proof?

Let $Rec(\Sigma)$ be the class of languages over $\Sigma^*$ recognizable by finite monoids. To show that $Rec(\Sigma)$ is closed under Kleene star, one would usually refer to the equivalence of ...
2
votes
1answer
235 views

Existence of an algorithm

I need to show that there exists a polynomial time algorithm that inputs a deterministic automata $A$, and decides if $A$ accepts a word w if and only if it also accepts any word obtained by permuting ...
7
votes
1answer
209 views

Finding a minimal DFA whose language has a desired intersection with another

Suppose I have regular languages $B \subseteq A$, with corresponding (known) minimal deterministic finite automata $M_A, M_B$. I would like to find another regular language $C$ such that $B = A \cap ...
-1
votes
1answer
46 views

Push Down Automata [closed]

Can we put more than one element in stack at a time. Actually I am asking that this transition function is valid for PDA: ∆(q,a,z)=(q',aaz) Where: q and q' are states a is input symbol z is starting ...
3
votes
0answers
94 views

Looking for a specific tree automata model

is there any tree automata model over unranked trees (that is with unbounded number of children for each node), such that: Checking non-emptiness and universality is decidable in elementary time, ...
23
votes
2answers
522 views

Testing whether letters can be scheduled to achieve a word in a regular language

I fix a regular language $L$ on an alphabet $\Sigma$, and I consider the following problem that I call letter scheduling for $L$. Informally, the input gives me $n$ letters and an interval for each ...
4
votes
1answer
344 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
94 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
717 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
159 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 =...
7
votes
1answer
136 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)...
1
vote
1answer
111 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
69 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
75 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 ...
5
votes
1answer
199 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 ...
2
votes
1answer
219 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 $\...
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....
9
votes
3answers
295 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
98 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
101 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
430 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
225 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 ...
9
votes
1answer
290 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
81 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 \}$ ...
1
vote
2answers
61 views

Algorithms to synthesize optimal plans satisfying temporal logic constraints

I know how NuSMV can be applied on a model to check if certain temporal logic statements are satisfied, particularly LTL. I also know of the LTL to BA conversion routines available online. I am ...
8
votes
1answer
731 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$ : ...
7
votes
1answer
180 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 $...
9
votes
1answer
217 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 ...
16
votes
1answer
929 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 ...
7
votes
2answers
683 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 ...
9
votes
2answers
295 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 ...
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 ...
7
votes
1answer
474 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-...
5
votes
0answers
143 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 ...
2
votes
1answer
272 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
410 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 ...
1
vote
0answers
174 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 ...
17
votes
2answers
271 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 ...
6
votes
2answers
176 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 ...
3
votes
0answers
199 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 ...
14
votes
4answers
606 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
1answer
90 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
52 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
1
vote
0answers
122 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
2answers
234 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 $\...

1
2
3 4 5
7