Tag Info

15

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.

14

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

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 ...

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 ...

8

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 ...

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 http://www.liafa.univ-paris-diderot.fr/~jep/...

8

My KBMAG package can compute a finite state automaton that accepts the language of geodesic words in a hyperbolic group, and I think the states of that automaton correspond exactly to the conetypes. It is not particularly easy to use. If you write down the presentation of the group you are interested in, then I can try out the computation for 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 ...

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 ...

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}$. ...

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

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

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

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 ...

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

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.

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

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 ...

5

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 ...

4

"combinatory logic"

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.

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

Initial observation. Let me start by explaining that the answer to your final question is that no, the complement of $L_2$ does not have the pumping property. To see this, suppose that it had a pumping number $p$, so that any string of length at least $p$ in the complement of $L_2$ could be pumped. That is, if $w$ has length at least $p$ and is in the ...

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

This paper might be relevant: http://arxiv.org/abs/1508.06780. It studies the complementation result for automata over infinite trees, rather than words. There is a remark in this paper (page 11) concerning determinization of Buchi automata over ω-words: We have not attempted a careful verification, but we believe that the proof of determinization ...

3

I am not familiar with all proofs of McNaughton's theorem, but the ones I have seen use the weak form of Konig's Lemma that a finitely branching infinite tree contains an infinite path.

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

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

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 \$\...

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