This link has been bookmarked by 9 people . It was first bookmarked on 04 Aug 2008, by Sam Kitonyi.
-
07 Jul 17
-
that is, have a middle section of the word repeated an arbitrary number of times—to produce a new word that also lies within the same language
-
For a practical test that exactly characterizes regular languages, see the Myhill-Nerode theorem. The typical method for proving that a language is regular is to construct either a finite state machine or a regular expression for the language.
-
-
13 Apr 13
carlos puentes"In the theory of formal languages, the pumping lemma for regular languages describes an essential property of all regular languages. Informally, it says that all sufficiently long words in a regular language may be pumped — that is, have a middle section of the word repeated an arbitrary number of times — to produce a new word which also lies within the same language."
-
11 Feb 10
-
04 Aug 08
-
For example the language L = {anbn : n ≥ 0} over the alphabet Σ = {a, b} can be shown to be non-regular as follows. Let w, x, y, z, p, and i be as stated in the pumping lemma above. Let w in L be given by w = apbp. By the pumping lemma, there must be some decomposition w = xyz with |xy| ≤ p, |y| ≥ 1 such that xyiz in L for every i ≥ 0. If we let |xy|=p and |z|=p, then xy is the first half of w, or all p of the as. Because |y| ≥ 1, it consists of a non-zero number of as, and xy2z has more as than bs and is therefore not in L (note that any value of i ≠ 1 will give us a contradiction). We have reached a contradiction because, in this case, the pumped word does not belong to the language L. Therefore, the assumption that L is regular must be incorrect. Hence L is not regular.
The proof that the language of balanced (i.e., properly nested) parentheses is not regular follows the same idea. Given p, there is a string of balanced parentheses that begins with more than p left parentheses, so that y will consist entirely of left parentheses. By repeating y, we can produce a string that does not contain the same number of left and right parentheses, and so they cannot be balanced.
-
Would you like to comment?
Join Diigo for a free account, or sign in if you are already a member.