Languages That Are and Are Not RegularThe Pumping Lemma for Regular LanguagesA Complete Proof Using the Pumping LemmaDon’t Try to Use Closure BackwardsDistribution of |x| + q|y| + |z|:Automata Theory is Just the ScaffoldingLanguages That Are and Are Not RegularRead L & S 2.5, 2.6Read Supplementary Materials: Regular Languages and Finite State Machines: The Pumping Lemma for Regular Languages.Do Homework 9.Deciding Whether a Language is RegularTheorem: There exist languages that are not regular.Lemma: There are an uncountable number of languages.Proof of Lemma: Let: be a finite, nonempty alphabet, e.g., {a, b, c}.Then * contains all finite strings over . e.g., {, a, b, c, aa, ab, bc, abc, bba, bbaa, bbbaac}* is countably infinite, because its elements can be enumerated one at a time, shortest first.Any language L over is a subset of *, e.g., L1 = {a, aa, aaa, aaaa, aaaaa, …} L2 = {ab, abb, abbb, abbbb, abbbbb, …}The set of all possible languages is thus the power set of *.The power set of any countably infinite set is not countable. So there are an uncountable number of languages over *.Some Languages Are Not RegularTheorem: There exist languages that are not regular.Proof:(1) There are a countably infinite number of regular languages. This true because every description of a regular language is of finite length, so there is a countably infinite number of such descriptions.(2) There are an uncountable number of languages.Thus there are more languages than there are regular languages. So there must exist some language that is not regular.Showing That a Language is RegularTechniques for showing that a language L is regular:1. Show that L has a finite number of elements.2. Exhibit a regular expression for L.3. Exhibit a FSA for L.4. Exhibit a regular grammar for L.5. Describe L as a function of one or more other regular languages and the operators , , , *, -, . We use here the fact thatthe regular languages are closed under all these operations.6. Define additional operators and prove that the regular languages are closed under them. Then use these operators as in 5.ExampleLet = {0, 1, 2, … 9}Let L * be the set of decimal representations for nonnegative integers (with no leading 0's) divisible by 2 or 3.L1 = decimal representations of nonnegative integers without leading 0's.L1 = 0 {1, 2, … 9}{0 - 9}*So L1 is regular.L2 = decimal representations of nonnegative integers without leading 0's divisible by 2L2 = L1 *{0, 2, 4, 6, 8}So L2 is regular.Lecture Notes 8 Languages That Are and Are Not Regular 1Example, ContinuedL3 = L1 and divisible by 3Recall that a number is divisible by 3 if and only if the sum of its digits is divisible by 3. We can build a FSM to determine thatand accept the language L3a, which is composed of strings of digits that sum to a multiple of 3.L3 = L1 L3aFinally, L = L2 L3Another Example = {0 - 9}L = {w : w is the social security number of a living US resident}Finiteness - Theoretical vs. PracticalAny finite language is regular. The size of the language doesn't matter.Parity Soc. Sec. #Checking CheckingBut, from an implementation point of view, it very well may.When is an FSA a good way to encode the facts about a language?What are our alternatives?FSA's are good at looking for repeating patterns. They don't bring much to the table when the language is just a set of unrelated strings.Showing that a Language is Not RegularThe argument, “I can't find a regular expression or a FSM”, won't fly. (But a proof that there cannot exist a FSM is ok.)Instead, we need to use two fundamental properties shared by regular languages:1. We can only use a finite amount of memory to record essential properties.Example:anbn is not regular2. The only way to generate/accept an infinite language with a finite description is to use Kleene star (in regular expressions) or cycles (in automata). This forces some kind of simple repetitive cycle within the strings.Example:ab*a generates aba, abba, abbba, abbbba, etc.Example:{an : n 1 is a prime number} is not regular.Lecture Notes 8 Languages That Are and Are Not Regular 2Exploiting the Repetitive Property b b a a bIf a FSM of n states accepts any string of length n, how many strings does it accept?L = bab*ab n_ _ _ _ _ _ _ _b a b b b b a b x y zxy*z must be in L.So L includes: baab, babab, babbab, babbbbbbbbbbabThe Pumping Lemma for Regular LanguagesIf L is regular, then N 1, such that strings w L, where |w| N, x, y, z, such that w = xyzand |xy| N, and y ,and q 0, xyqz is in L.Example: L = anbna a a a a a a a a a b b b b b b b b b b x y z N 1 Call it N long strings w We pick one x, y, z We show no x, y, zExample: anbn is not RegularN is the number from the pumping lemma (or one more, if N is odd).Choose w = aN/2bN/2. (Since this is what it takes to be “long enough”: |w| N) 1 2a a a a a a a a a a b b b b b b b b b b x y zWe show that there is no x, y, z with the required properties:|xy| N, y , q 0, xyqz is in L.Three cases to consider: y falls in region 1: y falls across regions 1 and 2: y falls in region 3:Lecture Notes 8 Languages That Are and Are Not Regular 3Example: anbn is not RegularSecond try:Choose w to be be aNbN. (Since we get to choose any w in L.) 1 2a a a a a a a a a a b b b b b b b b b b x y zWe show that there is no x, y, z with the required properties:|xy| N, y , q 0, xyqz is in L.Since |xy| N, y must be in region 1. So y = ag for some g 1. Pumping in or out (any q but 1) will violate the constraint that the number of a’s has to equal the number of b’s.A Complete Proof Using the Pumping LemmaProof that L = {anbn} is not regular:Suppose L is regular. Since L is regular, we can apply the pumping lemma to L. Let N be the number from the pumping lemma for L. Choose w = aNbN. Note that w L and |w| N. From the pumping lemma, there exists some x, y, z where xyz = w and |xy| N, y , and q 0, xy q z L. Because |xy| N, y = a|y| (y is all a’s).
View Full Document
Unlocking...