# prof. busch - lsu1 more applications of the pumping lemma

Post on 21-Dec-2015

212 views

Category:

## Documents

Embed Size (px)

TRANSCRIPT

• Slide 1
• Prof. Busch - LSU1 More Applications of the Pumping Lemma
• Slide 2
• Prof. Busch - LSU2 The Pumping Lemma: Given a infinite regular language there exists an integer (critical length) for any string with length we can write with and such that:
• Slide 3
• Prof. Busch - LSU3 Regular languages Non-regular languages
• Slide 4
• Prof. Busch - LSU4 Theorem: The language is not regular Proof: Use the Pumping Lemma
• Slide 5
• Prof. Busch - LSU5 Assume for contradiction that is a regular language Since is infinite we can apply the Pumping Lemma
• Slide 6
• Prof. Busch - LSU6 We pick Let be the critical length for Pick a string such that: lengthand
• Slide 7
• Prof. Busch - LSU7 we can write: with lengths: From the Pumping Lemma: Thus:
• Slide 8
• Prof. Busch - LSU8 From the Pumping Lemma: Thus:
• Slide 9
• Prof. Busch - LSU9 From the Pumping Lemma: Thus:
• Slide 10
• Prof. Busch - LSU10 BUT: CONTRADICTION!!!
• Slide 11
• Prof. Busch - LSU11 Our assumption that is a regular language is not true Conclusion: is not a regular language Therefore: END OF PROOF
• Slide 12
• Prof. Busch - LSU12 Regular languages Non-regular languages
• Slide 13
• Prof. Busch - LSU13 Theorem: The language is not regular Proof: Use the Pumping Lemma
• Slide 14
• Prof. Busch - LSU14 Assume for contradiction that is a regular language Since is infinite we can apply the Pumping Lemma
• Slide 15
• Prof. Busch - LSU15 We pick Let be the critical length of Pick a string such that: length and
• Slide 16
• Prof. Busch - LSU16 We can write With lengths From the Pumping Lemma: Thus:
• Slide 17
• Prof. Busch - LSU17 From the Pumping Lemma: Thus:
• Slide 18
• Prof. Busch - LSU18 From the Pumping Lemma: Thus:
• Slide 19
• Prof. Busch - LSU19 BUT: CONTRADICTION!!!
• Slide 20
• Prof. Busch - LSU20 Our assumption that is a regular language is not true Conclusion: is not a regular language Therefore: END OF PROOF
• Slide 21
• Prof. Busch - LSU21 Regular languages Non-regular languages
• Slide 22
• Prof. Busch - LSU22 Theorem: The language is not regular Proof: Use the Pumping Lemma
• Slide 23
• Prof. Busch - LSU23 Assume for contradiction that is a regular language Since is infinite we can apply the Pumping Lemma
• Slide 24
• Prof. Busch - LSU24 We pick Let be the critical length of Pick a string such that: length
• Slide 25
• Prof. Busch - LSU25 We can write With lengths From the Pumping Lemma: Thus:
• Slide 26
• Prof. Busch - LSU26 From the Pumping Lemma: Thus:
• Slide 27
• Prof. Busch - LSU27 From the Pumping Lemma: Thus:
• Slide 28
• Prof. Busch - LSU28 Since: There must exist such that:
• Slide 29
• Prof. Busch - LSU29 However:for for any
• Slide 30
• Prof. Busch - LSU30 BUT: CONTRADICTION!!!
• Slide 31
• Prof. Busch - LSU31 Our assumption that is a regular language is not true Conclusion: is not a regular language Therefore: END OF PROOF
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://vdocuments.net/prof-busch-lsu1-more-applications-of-the-pumping-lemma.html", "fetch_time": 1585966137000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2020-16/segments/1585370519111.47/warc/CC-MAIN-20200404011558-20200404041558-00392.warc.gz", "warc_record_offset": 745073716, "warc_record_length": 17742, "token_count": 852, "char_count": 3003, "score": 3.953125, "int_score": 4, "crawl": "CC-MAIN-2020-16", "snapshot_type": "latest", "language": "en", "language_score": 0.7212144136428833, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00028-of-00064.parquet"}