Regular Language - Identify Nonregular Languages

Closure Properties of Regular Languages

封閉性

1. Union
   • 
2. Concatenation
   • 
3. Star Operation
   • 
4. Reverse
   • 
5. Complement
   • Complement
6. Intersection and Difference
   • Step.
     • 
     • 
     • 
     • 
   • 
   • 

封閉性在其他運算下

Def 4.1

Theorem 4.3

Elementary Questions about Regular Languages

Standard Representations

Question

Membership?

Is language empty?

Is language finite?

Is language1 == language2?

explain

• 

Identifying Nonregular Languages

Intro

The Pigeonhole Principle and DFAs

Intro

• 
• 

Example

• 

Pumping Lemma

Pumping Lemma Game

Applications of the Pumping Lemma

Step.

• 
• 
• 
• 
• 
• 

Common Pitfalls Using Pumping Lemma

• Use pumping lemma to show that a language is regular
• Start with a string not in L
• Make some assumptions about the decomposition xyz