# Tagged Questions

The tag has no usage guidance.

130 views

### Neighbourhood of a word and Levenshtein distance

The Levenshtein distance or Edit distance $$lev(U,V)$$ between two strings $U$ and $V$ over a finite alphabet $\Sigma$ of size $\left| \Sigma \right| = \sigma ,$ is the minimal number of insertions,...
191 views

### Non-regular languages fulfilling the Pumping Lemma

Some non-regular languages don't yield to the Pumping Lemma ($L_1=a^nb^mc^m$ should work). But now consider the set of non-regular languages L only over the alphabet {a}. (Like $L_2=a^{n^2}$ or ...
101 views

130 views

### Subsets of $\omega$-regular lanuages accepted by automata with special acceptance condition

Let $\mathcal A = (X, Q, \delta, q_0, F)$ be a deterministic finite automata with the following acceptance condition on infinite words: The automata accepts $\xi \in X^{\omega}$ with respect to $F$ ...
143 views

### Optimum control of a probabilistic automaton

Suppose we have a probabilistic automaton and we assign a weight to each state. An "interaction strategy" would be a fixed map from states to inputs. Any interaction strategy could be used to ...
249 views

### Proof that the $\omega$-language consisting of all words containing every finite word as a factor is not rational/regular

Let $\eta$ be an $\omega$-word over $X = \{0,1\}$ and let $F_k(\eta)$ denote the factors of $\eta$ of length $k$. Define the following $\omega$-languages  L_k := \{ \xi : F_k(\xi) = X^k \} = \{ \xi ...
126 views

### Varieties of rational languages and (pseudo-)varieties of finite monoids, question regarding closure property

Let $\mathcal Rat(A)$ denote the class of rational (or regular) languages over the alphabet $A$, a subset $\mathcal V(A) \subseteq \mathcal Rat(A)$ is called a variety of (rational) languages iff ...
559 views

### Isomorphism in category of finite automata

What does meanthat two finite automata is equivalent? I think that we must define category of finite automata, i.e. we must define $\mathrm{Hom}(A,B)$, where $A,B$ be an arbitrary finite automata. ...
184 views

### What is this structure called?

(I'm not entirely sure what to tag this; feel free to retag.) While thinking about automata (specifics below), I ran into the following phenomenon: A cofunction system is a pair of sets $X, A$, ...
215 views

### Is it decidable whether the support of a rational $\mathbb{Z}$-series is a regular language?

Let $S \in \mathbb{Z}\langle\langle A\rangle\rangle$ be a rational series in noncommutative variables. The support of $S$ is the set of all words $u \in A^*$ such that $(S, u) \not= 0$. It is ...
98 views

### Schönhage's SMM with only one instruction

It is possible to implement $\lambda$-calculus in Schönhage's storage modification machine using an infinite set of nodes and one single program consisted exclusively of (about hundred) instructions ...
658 views

### Turing-complete primitive blind automata

Let $N$ be the set of natural numbers, $S$ be the set of finite binary sequences, and $Q = [N \rightarrow N] \times [N \rightarrow N],$ where $[N \rightarrow N]$ is the set of all computable ...
666 views

### Collatz conjecture— finite state machine transducer construction, origination?

wikipedia has an entry on the Collatz conjecture with a section on As an abstract machine that computes in base two. this apparently describes a construction of a FSM transducer computing sequential ...
104 views

347 views

### prove (a+b)*=a*(ba*)* [closed]

formal language and automata theory regular expessions (a+b)* =a*(ba*)* please answer I want the proof thank you