Which proof technique has been used to prove that the class of regular languages is closed under the star operation?

Part 1: Automata and Languages

Chapter 1: Regular Languages

Section 1.1b: Regular Operations and Closure

Section Goals

• Define regular operations


• Define closure


• Consider the closure of regular operations


• Motivation: Later we will use regular operations as we define regular expressions (which are another way of defining regular languages)

Regular Operations: Definition

• What are Operations
• Arithmetic operations create a new value from 1 or 2 existing values (eg 2 + 3)
• Regular operations create a new language from 1 or 2 existing languages


• We define three regular operations (using languages A and B):
1. Union:
   A ∪ B = { x | x ∈ A or x ∈ B }


2. Concatenation:
   A ο B = { xy | x ∈ A and y ∈ B }


3. Star:
   A* = { x1x2...xk | k ≥ 0 and each xi ∈ A }


4. Languages A and B don't have to be regular
• Soon we'll see why these operations are called regular operations

Notes on Star

• Defined for all k and all xi


• What string is x1x2...xk with k=0?
• This is the empty string since it's the empty sequence of strings
• An equivalent definition of star is
  A* = {ε} ∪ { x1x2...xk | k > 0 and each xi ∈ A }

Regular Operations: Example

• Σ = {a, b, ..., z}


• A = {good, bad}
• B = {boy, girl}


• A ∪ B = ...
• B ∪ A = ...


• A ο B = ...
• B ο A = ...


• A* = ...


• B* = ...

Regular Operations: More Information

• The result of star always contains ε


• When does star not result in an infinite set?


• Star aka Kleene Star


• Wildcards!

The Term Closed for Sets Under Operations

• Example: Positives and arithmetic operations:
• Positives are closed under addition and multiplication


• Positives are not closed under subtraction
• Division - depends on whether the result is truncated


• A set is closed under an operation if applying the operation to any element(s) of the set yields an element in the set

Closure and Regular Operation

• Can we prove that the Regular Languages are closed under the Regular Operations


• First try Union, then (eventually) Concatenation and Star
• That is, the union of 2 regular languages is a regular language

Theorem 1.25:

Regular Languages Closed under Regular Operation Union

• Theorem 1.25: The class of Regular Languages is closed under the union operation


• Theorem 1.25 (restated): If A and B are regular languages, then so is A ∪ B


• Since A and B are regular, there are machines MA and MB that recognize them.


• Proof Idea:
• Use FSMs MA and MB to create FSM M3
• M3 recognizes the union of A and B
• M3 accepts a string if either MA or MB does.
• M3 simulates running both machines simultaneously.
• Intuition: keep one finger in each machine during execution

Regular Languages Closed under Union - Examples

• Example 1: Regular languages A = {0}* and B = {1}*, Σ = {0,1}
• What machine recognizes A?
• What machine recognizes B?


• Draw FSM M3 that recognizes A ∪ B
• Define Q3, new states that represent cross products of states
• Define Σ, q0, F
• Define Delta: Domain, codomain, and operations


• Example 2: Regular languages C = 0w and D = w0 where w is a non empty string from Σ
• What machine recognizes C?
• What machine recognizes D?


• Draw FSM M3 that recognizes C ∪ D

Regular Languages Closed under Union - General Solution

• Draw FSM M3 that recognizes A ∪ B
• Define Q3, new states that represent cross products of states
• Define Σ, q0, F
• Define Delta: Domain, codomain, and operations


• Define computatation for M3

Regular Languages Closed under Union - Proof

• We must prove that M3 recognizes exactly A ∪ B
• We must prove it recognizes all of A ∪ B and only A ∪ B


• This requires 2 steps:
1. Prove: if x ∈ A ∪ B then M3 recognizes x
2. Prove: if M3 recognizes x then x ∈ A ∪ B


• In other words, we prove: L(M3) = A ∪ B
• Prove: if x ∈ A ∪ B then x ∈ L(M3)
• Prove: if x ∈ L(M3) then x ∈ A ∪ B


• Let's prove it (with a little hand waving)

Theorem 1.26:

Regular Languages Closed under Concatenation

• Theorem 1.26: The class of Regular Languages is closed under the concatenation operation


• Theorem 1.26 (restated): If A and B are regular languages, then so is A ο B


• Proof Idea: Use FSMs for A and B to create a machine that recognizes the union


• Possible method: Use final state of machine for A as the initial state for B
• Problem 1: When to switch from the first machine to the second


• Problem 2: Merged state would need two transitions for each input symbol


• Problem 3: What if there are multiple final states


• Solution to both problems: Nondeterminism - A new tool!
• Allow epsilon transitions from first machine's final states to second machine's initial state
• This also allows a simple solution to the union problem


• Notes on nondeterminism (Section 1.2)

Which proof technique has been used to prove that the class of regular languages is closed under star operation?

How do you prove an operation is closed for regular language?

Which proof technique has been used to prove that the class of regular languages?

What operations are closed under regular languages?