Timeline for Regular languages and the pumping lemma
Current License: CC BY-SA 2.5
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 14, 2017 at 7:23 | comment | added | Sam Nead | For a tight discussion of disambiguation (by David Eppstein, of course!), see here: mathoverflow.net/a/45163/1650 . For a discussion of why a regular language has a rational generating function, see Stanley's discussion of the "transfer-matrix method''; you can find it as Theorem 4.7.2 of EC Vol I [page 242]. | |
| Nov 5, 2009 at 8:53 | comment | added | Yoo | As to intuition for regular languages (and hence also for sofic shifts), suppose a very long word is displayed on a screen one letter at a time (let's say you can press a button to see the next letter, but no buttons for going back), if you can decide if the word is in L with a bounded amount of memory (either your memory or jotting things down and erasing on physical papers), then the language L is regular. And if you write your decision algorithm in an automata, you will only need a finite number of states because your algorithm requires a bounded amount of memory. | |
| Oct 22, 2009 at 16:38 | comment | added | Tom Church | Diego de Estrada says "a regular language [is always unambiguous], because there exists a DFA that accepts it" on this page: mathoverflow.net/questions/563/… | |
| Oct 21, 2009 at 8:13 | comment | added | Tom Church | No: applying Myhill-Nerode, note that x^k and x^j can be distinguished by w^k. Thus this language is not regular. (I had misunderstood your question; I don't know if there is any regular language that is inherently ambiguous.) | |
| Oct 20, 2009 at 22:09 | comment | added | Qiaochu Yuan | Yes, but is it regular? I don't have much intuition for these things. | |
| Oct 20, 2009 at 21:57 | comment | added | Tom Church | According to Wikipedia, the language { x^ay^bz^cw^d | (a=d and b=c) or (a=b and b=c) } is inherently ambiguous. | |
| Oct 20, 2009 at 5:09 | comment | added | Reid Barton | Oh, it shouldn't be an issue because we can apply your second argument to a DFA which recognizes the language. | |
| Oct 20, 2009 at 5:05 | history | edited | Qiaochu Yuan | CC BY-SA 2.5 |
Fixed claim.
|
| Oct 20, 2009 at 5:04 | comment | added | Qiaochu Yuan | Hmm. According to Google there is a notion of "inherently ambiguous" language, which is a language with the property that every grammar describing it is ambiguous. But the search results I'm getting don't agree on whether there exist inherently ambiguous regular languages. | |
| Oct 20, 2009 at 4:53 | comment | added | Reid Barton | I'm curious about the "language is unambiguous" part. I would have thought that unambiguous-ness was a property of a grammar, not a language. What does "unambiguous" mean, and how do you prove it for the language of Dyck words? | |
| Oct 20, 2009 at 4:51 | comment | added | Andrew Critch | Simply awesome. Thanks for making me aware of this. | |
| Oct 20, 2009 at 4:47 | comment | added | Qiaochu Yuan | Flajolet and Sedgewick's text "Analytic Combinatorics" is available online here: algo.inria.fr/flajolet/Publications/books.html The proof can be done using both definitions of a regular language: if you define a regular language in terms of a regular grammar, this is equivalent to specifying the above generating function using sums, products, and the "Kleene star" 1/(1-x). If you define a regular language in terms of recognizability by a state machine G, then you can extract the generating function by considering 1/(I-At) where A is the adjacency matrix. | |
| Oct 20, 2009 at 4:29 | comment | added | Andrew Critch | THAT. IS. AWESOME. Where can I read more about this? | |
| Oct 20, 2009 at 4:26 | history | answered | Qiaochu Yuan | CC BY-SA 2.5 |