4 ms·
>there are non-regular languages that pass the pumping lemma test Can you give an example of that? You may be right, but I'm having a hard time coming up with
by algorias 15y ago
>there are non-regular languages that pass the pumping lemma test
Can you give an example of that? You may be right, but I'm having a hard time coming up with a language that is not regular but fulfils the pumping lemma.
- robinhouston 15y agoSure, there’s an example in the Wikipedia article linked from the footnote in my comment above: the language consisting of all strings over the alphabet {0,1,2,3} with a substring of length 3 including a duplicate character, as well as all strings over this alphabet where precisely 1/7 of the string's characters are 3's. As you can see, this example is a little complicated – and I don’t know a simpler one, so I’m not surprised you struggled to just come up with an example off the top of your head.