snippetMinor
How to pick w for the Pumping lemma if the language has no clear pattern?
Viewed 0 times
thelanguagehaspumpingforlemmahowclearpickpattern
Problem
I'm trying to understanding using the pumping lemma to prove that a language is not regular. I sort of understand how it works when the language describes strings with a particular form, like in this example, but what do you set w to if there isn't a particular form.
The particular problem I'm trying to prove isn't regular:
The language is the set of strings that is composed of 60% or more As and Bs with the alphabet {A, B, C, D}
Because the form of the strings is indeterminate (i.e. it doesn't follow a pattern like a^i b^i, I'm not sure how to divide the strings into a w and x, y, z.
The particular problem I'm trying to prove isn't regular:
The language is the set of strings that is composed of 60% or more As and Bs with the alphabet {A, B, C, D}
Because the form of the strings is indeterminate (i.e. it doesn't follow a pattern like a^i b^i, I'm not sure how to divide the strings into a w and x, y, z.
Solution
I think your confusion lies in the fact that the language is not given in more "structured" form. Even if the language is not given as such, you are free to choose any string from the language which is more "structured" and allows you to disprove that language is regular.
Take $w=C^{2N}A^{3N}$ (or $A^{3N}C^{2N}$) where $N$ is the pumping length and $w$ is a string in your language, and then follow the proof in similar lines as in How to prove that a language is not regular?.
You should prove by yourself that above string $w$ can not be pumped.
Take $w=C^{2N}A^{3N}$ (or $A^{3N}C^{2N}$) where $N$ is the pumping length and $w$ is a string in your language, and then follow the proof in similar lines as in How to prove that a language is not regular?.
You should prove by yourself that above string $w$ can not be pumped.
Context
StackExchange Computer Science Q#54579, answer score: 2
Revisions (0)
No revisions yet.