- Section 1.1 “The Regular Operations” and section 1.2
“Closure Under the Regular Operations”
- 3 regular operations: union, concatenation, Kleene star
- Concatenation = joining 2 strings
- Star denotes strings over alphabet (specifically all strings constructible by any number of concatenations of strings in language)
- Proof using Cartesian product of DFAs that set of regular languages closed under union
- Proof with NFAs that set of regular languages closed under union, and other regular operations
- 3 regular operations: union, concatenation, Kleene star
- Examples
- Machines used in following examples
- Union of languages accepted by machines M1 and M2
- Concatenation of languages accepted by M1 and M2
- Kleene star of language accepted by M1
- Machines used in following examples
- Other closure properties
- Is set of regular languages closed under intersection?
- Yes, footnote to text’s DFA construction for union
- Under complement?
- i.e., if L is regular, is Σ* - L regular?
- Let ( Q, Σ, δ, q0, F ) be DFA that recognizes L
- Construct ( Q, Σ, δ, q0, Q-F ) to recognize Σ* - L
- Under set difference?
- i.e., if L1 and L2 are regular, is L1 - L2 regular?
- Prove closure via already-proven closure properties
- Is set of regular languages closed under intersection?
- Show that language over {a,b} consisting of all strings containing an odd number
of a’s and a multiple of 3 of b’s is regular
- This language is intersection of odd-number-of-a’s and multiple-of-3-b’s
languages, so is regular if they are
- This language is intersection of odd-number-of-a’s and multiple-of-3-b’s
languages, so is regular if they are
- Regular expressions — defining languages via regular operations
- Suppose Σ = { w1, …, wn }
- wi denotes a language { wi }
- ∅ denotes language {}
- L1 ∪ L2 denotes union
- L1L2 denotes concatenation
- L1* denotes Kleene star
- Read section 1.3 from start through “Formal Definition of a Regular Expression”