Introduction & Regular Languages

Alphabet (Σ): A finite, non-empty set of symbols.

Example: Σ = {0, 1} is the binary alphabet.

String: A finite sequence of symbols from an alphabet. The empty string is denoted by ε.

Example: "abba" is a string over Σ = {a, b} with length 4.

Language: Any subset of Σ* (set of all possible strings over alphabet Σ).

Example: L = {aⁿbⁿ | n ≥ 0} is a language over {a, b}.

Regular Expression: A notation for describing regular languages using:

• Basic elements: ∅ (empty language), ε (empty string), a (single symbol)
• Union (+): R₁ + R₂ means either R₁ or R₂
• Concatenation (·): R₁R₂ means R₁ followed by R₂
• Kleene Star (*): R* means zero or more repetitions of R

Precedence: * > Concatenation > Union

Example: (a+b)*abb represents all strings over {a,b} ending with "abb".

Σ* (Kleene Star)	Σ⁺ (Positive Closure)
All strings including empty string	All strings excluding empty string
Σ* = {ε, a, b, aa, ab, ...}	Σ⁺ = {a, b, aa, ab, ...}
Σ* = Σ⁺ ∪ {ε}	Σ⁺ = Σ* - {ε}

Regular languages are closed under the following operations:

1. Union: If L₁ and L₂ are regular, then L₁ ∪ L₂ is regular.

Proof: If R₁ and R₂ are REs, then R₁ + R₂ is RE for the union.

2. Concatenation: If L₁ and L₂ are regular, then L₁ · L₂ is regular.

Proof: RE R₁R₂ describes the concatenation.

3. Kleene Star: If L is regular, then L* is regular.

Proof: RE R* describes L*.

4. Complement: If L is regular, then L' = Σ* - L is regular.

Proof: In DFA for L, swap accepting and non-accepting states.

5. Intersection: If L₁ and L₂ are regular, then L₁ ∩ L₂ is regular.

Proof: Use De Morgan's Law: L₁ ∩ L₂ = (L₁' ∪ L₂')', or construct product DFA.

(i) Strings with odd number of 1s:

0*(10*10*)*10*

Explanation: Start with any 0s, then one 1 (making it odd), then pairs of 1s (staying odd).

(ii) Strings having substring "10" or "11":

(0+1)*(10+11)(0+1)*

Explanation: Any prefix, then 10 or 11, then any suffix.

(iii) Strings with no consecutive 1s:

(0+10)*(1+ε)

Explanation: Either 0s or "10" blocks, optionally ending with single 1.

(iv) Strings containing sequence "011":

(0+1)*011(0+1)*

(v) Strings whose length is a multiple of 3:

((0+1)(0+1)(0+1))* or ((0+1)³)*

(i) 1(0+1)*0:

All binary strings that start with 1 and end with 0.

Examples: 10, 100, 110, 1010, 1110, ...

(ii) (aa)*(bb)*(b):

Strings with even number of a's followed by odd number of b's.

Examples: b, aab, aabbb, aaaab, ...

(iii) (ab+ba)*:

Strings made by concatenating "ab" or "ba" any number of times (including empty string).

Examples: ε, ab, ba, abab, abba, baba, ...

(iv) (A-Z)(a-z)*(a+e+i+o+u):

Strings starting with uppercase letter, followed by any lowercase letters, ending with a vowel.

Examples: Aa, He, Hello, Indonesia, ...

Statement:

If L is a regular language, then there exists a constant p (pumping length) such that for every string s ∈ L with |s| ≥ p, s can be written as s = xyz where:

1. |xy| ≤ p
2. |y| > 0 (y is not empty)
3. For all i ≥ 0, xyⁱz ∈ L

Usage:

Used to prove a language is NOT regular by contradiction:

1. Assume L is regular
2. Choose a string s ∈ L with |s| ≥ p
3. For ALL ways to split s = xyz (satisfying conditions 1 & 2)
4. Show that some xyⁱz ∉ L
5. Contradiction → L is not regular

Example: Prove L = {aⁿbⁿ | n ≥ 0} is not regular.

Choose s = aᵖbᵖ. Since |xy| ≤ p, y consists only of a's.

Pumping: xy²z = aᵖ⁺|ʸ|bᵖ ∉ L (unequal a's and b's). Contradiction!

Step 1: Analyze the RE

• Must start with 0
• Followed by zero or more 0s
• Then zero or more (01 or 0)

Step 2: Break into components

• S generates initial "0"
• A handles "0*"
• B handles "(01+0)*"

Step 3: Write the grammar

Step 4: Simplify (combine B and C)

Step 5: Verify with examples

• "0" → S ⇒ 0A ⇒ 0
• "00" → S ⇒ 0A ⇒ 00A ⇒ 00
• "001" → S ⇒ 0A ⇒ 00A ⇒ 00B ⇒ 001A ⇒ 001

Given RLG:

Step 1: Construct FA from RLG

States: S (start), A, B, F (final)

Transitions:

• S --a--> A, S --b--> B
• A --a--> A, A --a--> F
• B --b--> B, B --b--> F

Step 2: Reverse the FA

New start: F, New final: S

Reversed transitions:

• A --a--> S, B --b--> S
• A --a--> A, F --a--> A
• B --b--> B, F --b--> B

Step 3: Write LLG from reversed FA

Language: a⁺ + b⁺ (one or more a's, OR one or more b's)