## Hot answers tagged automata-theory

14

Let Ln be the number of words in L of length n. If sum L_n x^n is not a rational function, then L can't be regular. See the proof in the comments.

13

For necessary and sufficient conditions for a language to be regular (sometimes useful in proving nonregularity when simpler tricks like the pumping lemma fail) see the Myhill–Nerode theorem.

10

I'm not an expert in the area, but here's a few highlights:
Bridson distinguished automatic and combable groups.
Burger and Mozes found examples of biautomatic simple groups.
Mapping class groups were originally shown to be automatic by Mosher. Recently, Hamenstadt has shown that they are biautomatic.
See part 3 of McCammond's survey for an update on ...

8

I gave a sequential machine computing the 3n+1/n:2 function in base 2 in several courses
since 1990, but of course I am not claiming any originality here, since it is just an easy
exercise.
Anyway, if you want to see in more details how this sequential machine can be computed in a systematic way, you can look at ...

8

[Edit, June 2, 2013: At the Nordic Spring School in Logic this year there was a course by Wolfgang Thomas on Logic, automata and games. You may be interested in the slides, particularly for part III (Rabin’s tree theorem). Slides and notes for all courses can be downloaded here; the slides for part III can be downloaded here.]
This is a nice result, but you ...

7

Without additional assumptions there is no such algorithm. In finite time an alleged algorithm could only test for finitely many inputs, but since there are infinitely many regular languages which match any given finite number of test cases, the algorithm cannot work.
In machine learning this is a common situation (given these finitely many cases of a ...

7

Yes (though the standard term for these is generating functions rather than zeta functions); in fact, there's a relatively straightforward explicit construction for finding the generating function for a regular language given an unambiguous regular expression for it; replace null with $0$, any symbol with $x$, concatenation by multiplication, union with ...

6

Cannon does more than just refer to result that you ask for, he sketches the proof out. His proof is couched in the notation that he has set up for his application to hyperbolic groups. But it is easy enough to unravel the notation and express the proof in general.
Label the state set of the automaton as $0,\ldots,N$ where $0$ is the start state. Consider ...

6

Start by making a deterministic finite automaton $M$. Now $n_k$ is the number of walks of length $k$ from the starting state to an accepting state, so $\sum n_k z^k$ is the sum of some entries of $(I-zA)^{-1}$, where $A=(a_{ij})$ is the integer matrix in which $a_{ij}$ is the number of transitions from state $i$ to state $j$. The entries you need to add are ...

6

Update. It is undecidable. Here is the proof.
If $f,g\colon A^*\to \{a,b\}^*$ are two morphisms, then one can construct a rational Z-series over A whose support is the complement of the equalizer of f,g. This is how Post correspondence is reduced to universality of $\mathbb{Z}$-series and is based on a faithful 2x2 rep of the free monoid over $\mathbb{N}$. ...

6

In recent years almost anything I have read about lambda calculus has been about typed lambda calculus. Broadly speaking, I think computer scientists would say that these papers were part of the field known as Type Theory.
If that doesn't quite fit what you want I'd suggest reading the PLT article on Wikipedia.
For example, there is a family of lambda ...

5

I don't know of one that seems sufficiently general. The theory's at an intersection:
It (in its untyped guise) is one of the four most important Turing-complete computation systems;
It is algebraically natural, connected fundamentally to Cartesian-closed categories (though with horrid baggage around $\alpha$-equivalence);
It is a foundational theory, ...

5

There is no such algorithm. As an explicit example, imagine a black box that always says yes. How many inputs should this algorithm test before it concludes that the language contains all words?
(NB: You write "given a language, is there an algorithm...". I read this as "Is there an algorithm which, given a language, ...".)

5

It seems to me that FV should be the variety of languages associated to $\mathcal R$-trivial monoids. A monoid is $\mathcal R$-trivial if Green's relation $\mathcal R$ is trivial. This is the same as satisfying $(xy)^{\omega}x=(xy)^{\omega}$ for all $x,y$ where $z^{\omega}$ is the idempotent power of $z$.
Suppose first that the language has finite ...

5

This is not really an answer but an attempt to clear away some of the underbrush and perhaps remove some confusion, so as to formulate the question in a more appropriate context.
As far as I can see, the question is simultaneously about two differences between Eilenberg's treatment of recursiveness and a traditional treatment in terms of (partial) functions ...

5

It seems that the answer to your question is no. See here.

5

We say that Alice catches the word if she can make the desired move. We prove that a protocol exists by the induction on $d=|\Sigma|$.
Your example states the base for $d=2$. Assume that we know Alice's strategy for $d-1$ letters; let $k'$ be the length of the words in the catching triples. Note that in fact Alice catches all the finite words of some length ...

4

This is of course a special case of the Chomsky-Schutzenberger theorem that unambiguous context-free languages have algebraic generating functions. Restricted to a regular language it is like this. Assume the automata has state set $1,...,n$. Let $1$ be the initial state for convenience. Let A be the adjacency matrix of the automaton, let $e_1$ be the ...

4

Let $A$ contain all even-length strings, plus an undecidable collection of odd-length strings. Let $B$ contain all odd-length strings, plus the empty string, plus an undecidable collection of even-length strings. So each is undecidable, but the concatenation $AB$ consists of all strings and hence is decidable.

3

Grammars involving the usual context-free operations plus intersection are called conjunctive grammars. Adding negation (in addition to intersection) gives boolean grammars.
Alexander Okhotin has done quite a bit of recent work on the closure properties of the languages (sets of strings) specified by these sorts of grammars. He also has a paper showing ...

3

Your first conjecture — the claim that does not insist on eventually periodic input — is not true.
For a counterexample, consider the language consisting of all infinite binary strings $\xi$, such that every infix maximal finite block of $0$s has even length. This language can be accepted by a machine according to your criterion, since we can ...

3

The usual pumping lemma gives only a necessary condition for a language to be regular,
but there are more powerful versions giving necessary and sufficient conditions, using "block pumping properties".
A. Ehrenfeucht, R. Parikh, and G. Rozenberg, Pumping lemmas for regular sets, SIAM
J. Comput. 10 (1981), 536-541.
S. Varricchio, A Pumping Condition for ...

3

You can always go through the $\omega$-semigroup. It might not be the most straightforward algorithm, but at least it should work.
You can find details in http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/DG-WT08.pdf
The principle is to translate your automaton into an $\omega$-semigroup, via the transition matrices for instance.
Then you can minimize this ...

3

No, ths is not true.
Let $E$ be a finite group and let $\phi:F_\Sigma\to E$ be a surjective group homomorphism. Let $A,B\subset E$ any subgroups and let $G=\phi^{-1}(A)$ and $H=\phi^{-1}(B)$.
If $GH=HG$ holds, then by applying $\phi$ we get $AB=BA$.
So if the claim was true, then for every pair of subgroups $A,B$ of any finite group we would have $AB=BA$.
...

3

You can find these notions, e.g, in the book
Ji.Adamek, V.Trnkova, Automata and Algebras in Categories. Kluwer, 1989,
S.Eilenberg, Automata, languages, and machines, v.A. Academic Press, 1974
and others books. In the first book there is also a more weak notion of equivalence -- automata with the same behavior.
Addendum: Let an automaton (with an initial ...

3

I think the confusion comes from the fact that a variety of languages is not $\mathcal V(A)$ for some fixed $A$, it is a mapping $\mathcal V: \mathit{Alphabets}\to \mathit{Sets~of~Languages}$, mapping each alphabet $A$ to a set of languages $\mathcal V(A)$.
Now it makes sense to say that $\mathcal V$ is closed under inverse morphisms.
The bijection of ...

3

Indeed, your language $L$ is not Büchi-recognizable. To see this, suppose that we have a finite state Büchi automata $M$ that recognizes all the strings in $L$. That is, $M$ is a finite state automata, and when we run $M$ on any string $s\in L$ we visit an accepting state of $M$ infinitely many times. Fix any particular string $s\in L$, so that $s$ is an ...

3

Your question is a bit unclear, and when we clarify it, it becomes true.
If by "deterministic context-free grammar" you mean, as usual, an LR(k) grammar for some k, then Knuth proved in his seminal paper ("On the translation of languages from left to right", 1965) that the languages defined are the same as those defined by deterministic PDAs. These are ...

3

Another good way to prove language L non-regular is to find a regular language A such that L∩A is non-regular.
For example, one can take A = a*b*, and prove that L∩A = {a^nb^n : n≥0}.
This method works because the intersection of two regular languages is always regular.

Only top voted, non community-wiki answers of a minimum length are eligible