CS402 — Midterm Summary (Lectures 1–22)

📘 Lecture 1 — Theory of Automata

📖 Overview: This introductory lecture establishes the fundamental building blocks of automata theory and formal languages. It defines key concepts like alphabets, strings, and words, and introduces the descriptive definition of languages through numerous examples, including important languages like EQUAL, EVEN-EVEN, PALINDROME, and others. Understanding these foundations is critical for analyzing computational problems and designing automata.

🗂️ Topics Covered

The lecture begins by defining automata as "something that works automatically" and distinguishes between formal (syntactic) and informal (semantic) languages. It progresses through definitions of alphabets as finite non-empty sets of symbols, strings as concatenations of letters, and words as strings belonging to a language. The distinction between valid and invalid alphabets is explained using tokenization examples. String length, reverse of a string, and various methods of defining languages are covered, with extensive examples including EQUAL, EVEN-EVEN, INTEGER, EVEN, {aⁿbⁿ}, {aⁿbⁿaⁿ}, factorial, FACTORIAL, DOUBLEFACTORIAL, SQUARE, DOUBLESQUARE, PRIME, and PALINDROME. The lecture concludes with a proof about palindrome counts.

📝 Lecture Summary

What does automata mean?

It is the plural of automaton, and it means "something that works automatically".

Introduction to languages

There are two types of languages: Formal Languages (Syntactic languages) and Informal Languages (Semantic languages).

Alphabets

🔑 Definition — Alphabet: A finite non-empty set of symbols (called letters), denoted by Σ (Greek letter sigma).

Example: Σ = {a,b}, Σ = {0,1} (important as this is the language which computers understand), Σ = {i,j,k}

Note: Certain version of language ALGOL has 113 letters. Σ (alphabet) includes letters, digits, and a variety of operators including sequential operators such as GOTO and IF.

Strings

🔑 Definition — String: Concatenation of a finite number of letters from the alphabet.

Example: If Σ = {a,b} then strings include a, abab, aaabb, ababababababababab

Note — Empty string or null string: Sometimes a string with no symbol at all is used, denoted by λ (small Greek letter lambda) or Λ (capital Greek letter lambda), called an empty string or null string. The capital lambda will mostly be used to denote the empty string in further discussion.

Words

🔑 Definition — Word: Words are strings belonging to some language.

Example: If Σ = {x} then a language L can be defined as L = {xⁿ : n = 1,2,3,...} or L = {x, xx, xxx,...}. Here x, xx, ... are the words of L.

Note: All words are strings, but not all strings are words.

Valid/Invalid Alphabets

While defining an alphabet, an alphabet may contain letters consisting of groups of symbols. For example, Σ₁ = {B, aB, bab, d} is a valid alphabet. Now consider Σ₂ = {B, Ba, bab, d} and a string BababB. This string can be tokenized in two different ways: (Ba)(bab)(B) or (B)(abab)(B). The second grouping cannot be identified as a string defined over Σ = {a, b} because when scanned by the compiler (Lexical Analyzer), the first symbol B is identified, but the lexical analyzer cannot identify the second letter, creating ambiguity.

Remarks: While defining an alphabet of letters consisting of more than one symbol, no letter should be started with a letter of the same alphabet (i.e., one letter should not be the prefix of another). However, a letter may end in a letter of the same alphabet.

Conclusion: Σ₁ = {B, aB, bab, d} is a valid alphabet, while Σ₂ = {B, Ba, bab, d} is an invalid alphabet.

Length of Strings

🔑 Definition — Length of a string: The length of string s, denoted by |s|, is the number of letters in the string.

Example 1: Σ = {a,b}, s = ababa, |s| = 5

Example 2: Σ = {B, aB, bab, d}, s = BaBbabBd, Tokenizing = (B)(aB)(bab)(B)(d), |s| = 5

Reverse of a String

🔑 Definition — Reverse of a string: The reverse of a string s, denoted by Rev(s) or sʳ, is obtained by writing the letters of s in reverse order.

Example 1: If s = abc defined over Σ = {a,b,c}, then Rev(s) or sʳ = cba

Example 2: Σ = {B, aB, bab, d}, s = BaBbabBd, Rev(s) = dBbabaBB

Defining Languages

Languages can be defined in different ways: Descriptive definition, Recursive definition, using Regular Expressions (RE), and using Finite Automaton (FA), etc.

Descriptive Definition of Language

The language is defined by describing the conditions imposed on its words.

Example 1: The language L of strings of odd length, defined over Σ = {a}, can be written as L = {a, aaa, aaaaa, ...}

Example 2: The language L of strings that do not start with a, defined over Σ = {a,b,c}, can be written as L = {Λ, b, c, ba, bb, bc, ca, cb, cc, ...}

Example 3: The language L of strings of length 2, defined over Σ = {0,1,2}, can be written as L = {00, 01, 02, 10, 11, 12, 20, 21, 22}

Example 4: The language L of strings ending in 0, defined over Σ = {0,1}, can be written as L = {0, 00, 10, 000, 010, 100, 110, ...}

Example 5: The language EQUAL, of strings with number of a's equal to number of b's, defined over Σ = {a,b}, can be written as {Λ, ab, ba, aabb, abab, baba, abba, ...}

Example 6: The language EVEN-EVEN, of strings with even number of a's and even number of b's, defined over Σ = {a,b}, can be written as {Λ, aa, bb, aaaa, aabb, abab, abba, baab, baba, bbaa, bbbb, ...}

Example 7: The language INTEGER, of strings defined over Σ = {-,0,1,2,3,4,5,6,7,8,9}, can be written as INTEGER = {..., -2, -1, 0, 1, 2, ...}

Example 8: The language EVEN, of strings defined over Σ = {-,0,1,2,3,4,5,6,7,8,9}, can be written as EVEN = {..., -4, -2, 0, 2, 4, ...}

Example 9: The language {aⁿbⁿ}, of strings defined over Σ = {a,b}, as {aⁿbⁿ : n = 1,2,3,...}, can be written as {ab, aabb, aaabbb, aaaabbbb, ...}

Example 10: The language {aⁿbⁿaⁿ}, of strings defined over Σ = {a,b}, as {aⁿbⁿaⁿ : n = 1,2,3,...}, can be written as {aba, aabbaa, aaabbbaaa, aaaabbbbaaaa, ...}

Example 11: The language factorial, of strings defined over Σ = {0,1,2,3,4,5,6,7,8,9}, i.e., {1, 2, 6, 24, 120, ...}

Example 12: The language FACTORIAL, of strings defined over Σ = {a}, as {aⁿ! : n = 1,2,3,...}, can be written as {a, aa, aaaaaa, ...}. Note that the language FACTORIAL can be defined over any single letter alphabet.

Example 13: The language DOUBLEFACTORIAL, of strings defined over Σ = {a, b}, as {aⁿ! bⁿ! : n = 1,2,3,...}, can be written as {ab, aabb, aaaaaabbbbbb, ...}

Example 14: The language SQUARE, of strings defined over Σ = {a}, as {aⁿ² : n = 1,2,3,...}, can be written as {a, aaaa, aaaaaaaaa, ...}

Example 15: The language DOUBLESQUARE, of strings defined over Σ = {a, b}, as {aⁿ² bⁿ² : n = 1,2,3,...}, can be written as {ab, aaaabbbb, aaaaaaaaabbbbbbbbb, ...}

Example 16: The language PRIME, of strings defined over Σ = {a}, as {aᵖ : p is prime}, can be written as {aa, aaa, aaaaa, aaaaaaa, aaaaaaaaaaa, ...}

An Important Language — PALINDROME

The language consisting of Λ and the strings s defined over Σ such that Rev(s) = s. The words of PALINDROME are called palindromes.

Example: For Σ = {a,b}, PALINDROME = {Λ, a, b, aa, bb, aaa, aba, bab, bbb, ...}

Remark: There are as many palindromes of length 2n as there are of length 2n-1.

To prove this remark, note the following: Number of strings of length 'm' defined over an alphabet of 'n' letters is nᵐ.

Example: The language of strings of length 2 defined over Σ = {a,b} is L = {aa, ab, ba, bb}, i.e., number of strings = 2² = 4. The language of strings of length 3 defined over Σ = {a,b} is L = {aaa, aab, aba, baa, abb, bab, bba, bbb}, i.e., number of strings = 2³ = 8.

To calculate the number of palindromes of length 2n: Consider a palindrome of length 2n. The first n letters can be any string of length n (there are 2ⁿ such strings), and the last n letters are determined as the reverse of the first n. Therefore, the number of palindromes of length 2n = 2ⁿ.

To calculate the number of palindromes of length (2n-1) with 'a' as the middle letter: There are as many palindromes of length 2n-1 as there are strings of length n-1 (the left half). So the number = 2ⁿ⁻¹. Similarly, the number of palindromes of length 2n-1 with 'b' as middle letter is also 2ⁿ⁻¹. Hence, the total number of palindromes of length 2n-1 = 2ⁿ⁻¹ + 2ⁿ⁻¹ = 2(2ⁿ⁻¹) = 2ⁿ.

This proves that the number of palindromes of length 2n equals the number of palindromes of length 2n-1, which is 2ⁿ.

💡 Why this matters: This counting principle shows the structural symmetry of palindromes and is useful for understanding the growth of language sizes.

⭐ Key Takeaways

The most critical concept from this lecture is that an alphabet is a finite non-empty set of symbols, and languages are sets of strings (words) formed from that alphabet. The distinction between valid and invalid alphabets hinges on whether any letter is a prefix of another letter, which would cause tokenization ambiguity. Languages can be defined descriptively by stating conditions on their words, as shown through numerous examples like EQUAL, EVEN-EVEN, and PALINDROME. For PALINDROME, the number of palindromes of length 2n equals the number of palindromes of length 2n-1, both equal to 2ⁿ. Finally, the null string (Λ) is a valid string and may or may not belong to a given language.

🧠 Quick Revision Questions

1. What is an alphabet, and what is the notation used to represent it?
2. Why is Σ₂ = {B, Ba, bab, d} considered an invalid alphabet? Explain the ambiguity in tokenizing the string BababB.
3. Define the reverse of a string. If s = BaBbabBd defined over Σ = {B, aB, bab, d}, what is Rev(s)?
4. List the first five words of the language PALINDROME defined over Σ = {a, b} that have length 4 or less.
5. Prove that the number of palindromes of length 2n is equal to the number of palindromes of length 2n-1 when defined over an alphabet of two letters.

📘 Lecture 2 — Summary

📖 Overview: This lecture introduces fundamental operations and definitions for constructing formal languages. It covers Kleene Star Closure and Plus operations, provides the recursive definition method for specifying languages, and presents multiple examples of defining specific languages like INTEGER, EVEN, PALINDROME, and languages with particular string properties.

🗂️ Topics Covered

The lecture covers Kleene Star Closure and its application to alphabets and sets of strings, the Plus operation as a variant of Kleene Star that excludes the null string, the three-step recursive definition process for defining languages, and numerous examples including INTEGER, EVEN, factorial, PALINDROME, {aⁿbⁿ}, and languages of strings ending in a, beginning and ending with same letters, containing aa or bb, and containing exactly one a.

📝 Lecture Summary

Kleene Star Closure

Given Σ, then the Kleene Star Closure of the alphabet Σ, denoted by Σ*, is the collection of all strings defined over Σ, including Λ. It is to be noted that Kleene Star Closure can be defined over any set of strings.

🔑 Definition — Kleene Star Closure (Σ*): The set of all possible strings (including the empty string Λ) that can be formed from a given alphabet or set of strings.

📐 Formula: Σ* = {Λ} ∪ Σ ∪ Σ² ∪ Σ³ ∪ ... → all finite-length strings including empty string

📌 Example: If Σ = {0,1}, then Σ* = {Λ, 0, 1, 00, 01, 10, 11, ....}

Note: Languages generated by Kleene Star Closure of set of strings are infinite languages. (By infinite language, it is supposed that the language contains infinite many words, each of finite length).

PLUS Operation (+)

Plus Operation is same as Kleene Star Closure except that it does not generate Λ (null string), automatically.

🔑 Definition — Plus Operation (Σ+): The set of all non-empty strings that can be formed from a given alphabet or set of strings.

📐 Formula: Σ+ = Σ ∪ Σ² ∪ Σ³ ∪ ... → all finite-length strings excluding empty string

📌 Example: If Σ = {0,1}, then Σ+ = {0, 1, 00, 01, 10, 11, ....}

Remark: It is to be noted that Kleene Star can also be operated on any string i.e. a* can be considered to be all possible strings defined over {a}, which shows that a* generates Λ, a, aa, aaa, ... It may also be noted that a+ generates a, aa, aaa, aaaa, ...

Recursive definition of languages

The following three steps are used in recursive definition: Some basic words are specified in the language. Rules for constructing more words are defined in the language. No strings except those constructed in above, are allowed to be in the language.

Defining language of INTEGER

Step 1: 1 is in INTEGER. Step 2: If x is in INTEGER then x+1 and x-1 are also in INTEGER. Step 3: No strings except those constructed in above, are allowed to be in INTEGER.

Defining language of EVEN

Step 1: 2 is in EVEN. Step 2: If x is in EVEN then x+2 and x-2 are also in EVEN. Step 3: No strings except those constructed in above, are allowed to be in EVEN.

Defining the language factorial

Step 1: As 0!=1, so 1 is in factorial. Step 2: n! = n*(n-1)! is in factorial. Step 3: No strings except those constructed in above, are allowed to be in factorial.

Defining the language PALINDROME, defined over Σ = {a,b}

Step 1: a and b are in PALINDROME Step 2: if x is palindrome, then s(x)Rev(s) and xx will also be palindrome, where s belongs to Σ* Step 3: No strings except those constructed in above, are allowed to be in palindrome

Defining the language {aⁿbⁿ}, n=1,2,3,..., of strings defined over Σ={a,b}

Step 1: ab is in {aⁿbⁿ} Step 2: if x is in {aⁿbⁿ}, then axb is in {aⁿbⁿ} Step 3: No strings except those constructed in above, are allowed to be in {aⁿbⁿ}

💡 Why this matters: The language {aⁿbⁿ} is a classic example of a non-regular language — it cannot be recognized by a finite automaton, making it a crucial benchmark in automata theory.

Defining the language L, of strings ending in a, defined over Σ={a,b}

Step 1: a is in L Step 2: if x is in L then s(x) is also in L, where s belongs to Σ* Step 3: No strings except those constructed in above, are allowed to be in L

Defining the language L, of strings beginning and ending in same letters, defined over Σ={a, b}

Step 1: a and b are in L Step 2: (a)s(a) and (b)s(b) are also in L, where s belongs to Σ* Step 3: No strings except those constructed in above, are allowed to be in L

Defining the language L, of strings containing aa or bb, defined over Σ={a, b}

Step 1: aa and bb are in L Step 2: s(aa)s and s(bb)s are also in L, where s belongs to Σ* Step 3: No strings except those constructed in above, are allowed to be in L

Defining the language L, of strings containing exactly one a, defined over Σ={a, b}

Step 1: a is in L Step 2: s(a)s is also in L, where s belongs to b* Step 3: No strings except those constructed in above, are allowed to be in L

⭐ Key Takeaways

The Kleene Star Closure Σ* generates all possible strings including the empty string Λ, while the Plus operation Σ+ generates all non-empty strings. Recursive definition of languages follows three essential steps: specifying basic words, providing construction rules, and restricting to only strings built from those rules. The choice of basic words and construction rules in step 1 and step 2 determines the language properties — for example, ending with 'a', beginning and ending with same letter, or containing exactly one 'a'. The Plus operation can be expressed as Σ+ = Σ* - {Λ}, making it a restricted version of Kleene Star.

🧠 Quick Revision Questions

1. What is the difference between Kleene Star Closure and Plus operation regarding the empty string Λ?
2. What are the three steps in the recursive definition of a language?
3. How would you define the language {aⁿbⁿ} recursively?
4. If Σ = {aaB, c}, list the first four strings in Σ+ (excluding Λ).
5. In the recursive definition of strings containing exactly one 'a', why is s restricted to b* in step 2?

📘 Lecture 3 — Theory of Automata

📖 Overview: This lecture introduces regular expressions (RE) as a formal way to describe languages, along with their recursive definition. It demonstrates how to construct REs for various languages, including those with specific constraints like containing certain letters, having specific lengths, or starting/ending with particular symbols.

🗂️ Topics Covered

Regular Expression, Recursive definition of RE, defining languages by RE, {x}, {x}+, {a+b}, Language of strings having exactly one a, Language of strings of even length, Language of strings of odd length, RE defines unique language (as Remark), Language of strings having at least one a, Language of strings having at least one a and one b, Language of strings starting with aa and ending in bb, Language of strings starting with and ending in different letters.

📝 Lecture Summary

Regular Expression

As discussed earlier that a* generates Λ, a, aa, aaa, ... and a+ generates a, aa, aaa, aaaa, ..., so the language L₁ = {Λ, a, aa, aaa, ...} and L₂ = {a, aa, aaa, aaaa, ...} can simply be expressed by a* and a+, respectively. a* and a+ are called the regular expressions (RE) for L₁ and L₂ respectively.

🔑 Definition — Regular Expression (RE): A formal notation used to describe a language by combining symbols from an alphabet using operators like concatenation, union (+), and Kleene star (*).

📌 Example: Note that a+, aa*, and a*a all generate the same language L₂ = {a, aa, aaa, aaaa, ...}.

Recursive definition of Regular Expression (RE)

Step 1: Every letter of Σ including Λ is a regular expression.
Step 2: If r₁ and r₂ are regular expressions then (r₁), r₁ r₂ (concatenation), r₁ + r₂ (union), and r₁* (Kleene star) are also regular expressions.
Step 3: Nothing else is a regular expression.

🔑 Definition — Recursive definition: A definition that builds complex objects from simpler ones using a base case (Step 1) and a recursive step (Step 2), with a closure condition (Step 3).

Method 3 (Regular Expressions)

Consider the language L={Λ, x, xx, xxx,...} of strings, defined over Σ = {x}. We can write this language as the Kleene star closure of alphabet Σ or L=Σ*={x}. This language can also be expressed by the regular expression x.

Similarly the language L={x, xx, xxx,...}, defined over Σ = {x}, can be expressed by the regular expression x+.

Now consider another language L, consisting of all possible strings, defined over Σ = {a, b}. This language can also be expressed by the regular expression (a + b)*.

Now consider another language L, of strings having exactly one a, defined over Σ = {a, b}, then its regular expression may be bab.

Now consider another language L, of even length, defined over Σ = {a, b}, then its regular expression may be ((a+b)(a+b))*.

Now consider another language L, of odd length, defined over Σ = {a, b}, then its regular expression may be (a+b)((a+b)(a+b))* or ((a+b)(a+b))*(a+b).

🔑 Definition — Kleene star closure: The set of all possible strings (including Λ) that can be formed by concatenating zero or more strings from a given alphabet.

📐 Formula: (a+b)* → The set of all strings of any length over {a, b} 📐 Formula: (a+b)((a+b)(a+b))* → The set of all strings of odd length over {a, b}

💡 Why this matters: Understanding how to translate a language description into a regular expression is fundamental for pattern matching and lexical analysis in compilers.

Remark

It may be noted that a language may be expressed by more than one regular expression, while given a regular expression there exists a unique language generated by that regular expression.

Example

Consider the language, defined over Σ = {a , b} of words having at least one a, may be expressed by a regular expression (a+b)a(a+b).

Consider the language, defined over Σ = {a, b} of words having at least one a and one b, may be expressed by a regular expression (a+b)*a(a+b)b(a+b) + (a+b)*b(a+b)a(a+b).

Consider the language, defined over Σ ={a, b}, of words starting with double a and ending in double b then its regular expression may be *aa(a+b)bb.

Consider the language, defined over Σ ={a, b} of words starting with a and ending in b OR starting with b and ending in a, then its regular expression may be **a(a+b)b + b(a+b)a.

⭐ Key Takeaways

Regular expressions are a powerful notation to describe languages, defined recursively using base alphabet symbols and operations of concatenation, union (+), and Kleene star (). A language can have multiple regular expressions, but each RE defines exactly one unique language. Key patterns include: (a+b) for all strings over {a,b}, bab for exactly one a, ((a+b)(a+b))* for even length strings, and (a+b)((a+b)(a+b))* for odd length strings. For constraints like "at least one a" use (a+b)a(a+b), and for "starting with aa and ending in bb" use aa(a+b)*bb.

🧠 Quick Revision Questions

1. What are the three steps in the recursive definition of a regular expression?
2. Write a regular expression for the language of all strings over {a,b} that have exactly one b.
3. What is the difference between (a+b)* and (a+b)+ in terms of the strings they generate?
4. Why can a language have more than one regular expression, but a regular expression defines only one language?
5. Write a regular expression for the language of all strings over {a,b} that start and end with different letters.

📘 Lecture 4 — Theory of Automata

📖 Overview: This lecture covers the EVEN-EVEN language and its regular expression, the critical difference between a*+b* and (a+b)*, and the formal definition of regular expressions and regular languages. It introduces the concept of finite automaton (FA) as a computational model, including its definition, transition table, and transition diagram.

🗂️ Topics Covered

The lecture begins with the regular expression of the EVEN-EVEN language, then clarifies the difference between a*+b* and (a+b)*. It defines equivalent regular expressions and demonstrates sum, product, and closure operations on regular expressions. The concept of regular languages is introduced, with the note that all finite languages are regular. Finally, the lecture introduces finite automaton, providing its formal definition, a transition table example, and a transition diagram.

📝 Lecture Summary

An important example

The language EVEN-EVEN is defined over Σ={a, b} and contains strings having an even number of a's and an even number of b's. Its strings include {Λ, aa, bb, aaaa, aabb, abab, abba, baab, baba, bbaa, bbbb,...}. The regular expression for EVEN-EVEN is: (aa+bb+(ab+ba)(aa+bb)(ab+ba))

💡 Why this matters: This is a classic example of a non-trivial regular language that requires careful construction of the regular expression.

Note

It is important to be clear about the difference between the following regular expressions:

• r₁ = a+b** generates strings that are either all a's or all b's (no mixing).
• r₂ = (a+b)* generates strings consisting of any concatenation of a and b (including mixed strings). Here r₁ does not generate any string that is a concatenation of a and b, while r₂ generates such strings.

🔑 Definition — Difference between a+b and (a+b)**: a+b* generates only strings of all a's or all b's, while (a+b)* generates any string of a's and b's.

Equivalent Regular Expressions

🔑 Definition — Equivalent Regular Expressions: Two regular expressions are said to be equivalent if they generate the same language.

📌 Example: Consider r₁ = (a + b)* (aa + bb) and r₂ = (a + b)*aa + (a + b)*bb. Both regular expressions define the language of strings ending in aa or bb.

Note

If r₁ = (aa + bb) and r₂ = (a + b) then:

• r₁ + r₂ = (aa + bb) + (a + b)
• r₁ r₂ = (aa + bb)(a + b) = (aaa + aab + bba + bbb)
• (r₁)* = (aa + bb)*

Regular Languages

🔑 Definition — Regular Language: The language generated by any regular expression is called a regular language.

It is to be noted that if r₁, r₂ are regular expressions, corresponding to the languages L₁ and L₂, then the languages generated by r₁ + r₂, r₁ r₂ (or r₂ r₁), and r₁* (or r₂*) are also regular languages.

🔑 Definition — Operations on Regular Languages: If L₁ and L₂ are expressed by r₁ and r₂ respectively, then:

• The language expressed by r₁ + r₂ is L₁ ∪ L₂
• The language expressed by r₁ r₂ is L₁ L₂, strings obtained by prefixing every string of L₁ with every string of L₂
• The language expressed by r₁* is L₁*, strings obtained by concatenating strings of L, including the null string

📌 Example: If r₁ = (aa+bb) and r₂ = (a+b), then the language generated by r₁+r₂ is regular, expressed by (aa+bb) + (a+b). The language generated by r₁ r₂ is regular, expressed by (aa+bb)(a+b). The language generated by r* (where r = aa+bb) is regular, expressed by (aa+bb)*.

All finite languages are regular

📌 Example: Consider the language L, defined over Σ={a,b}, of strings of length 2, starting with a. Then L = {aa, ab}, which may be expressed by the regular expression aa+ab. Hence L, by definition, is a regular language.

It may be noted that if a language contains even a thousand words, its RE may be expressed by placing '+' between all the words. The special structure of RE is not important here.

📌 Example: Consider L = {aaa, aab, aba, abb, baa, bab, bba, bbb}, which may be expressed by RE aaa+aab+aba+abb+baa+bab+bba+bbb, which is equivalent to (a+b)(a+b)(a+b).

Introduction to Finite Automaton

A finite automaton is introduced using a game board analogy with 64 boxes, pieces of paper (white and black), a finite number of arrangements, a pair of dice generating numbers 2-12, and transition rules among arrangements. Winning depends on the sequence of numbers generated.

Method 4 (Finite Automaton)

🔑 Definition — Finite Automaton (FA): A collection of:

1. Finite number of states, having one initial and some (maybe none) final states
2. Finite set of input letters (Σ) from which input strings are formed
3. Finite set of transitions: for each state and for each input letter, there is a transition showing how to move from one state to another

📌 Example: Σ = {a,b}, States: x, y, z where x is an initial state and z is a final state. Transitions:

• At state x reading a, go to state z
• At state x reading b, go to state y
• At state y reading a or b, go to state y
• At state z reading a or b, go to state z

Transition Table:

Transition Diagram:

        b          a,b
x- ──────────► y
         │         ▲
         │         │
         │a        │a,b
         ▼         │
         z+ ───────┘

This FA accepts the language of strings, defined over Σ={a,b}, starting with a. This language may be expressed by the regular expression a(a+b)*.

💡 Why this matters: Finite automata provide a visual and mathematical model for regular languages, connecting regular expressions to state machines.

⭐ Key Takeaways

The EVEN-EVEN language has a specific regular expression that ensures both a's and b's counts are even, demonstrating a non-trivial pattern. The critical distinction between a*+b* (only homogeneous strings) and (a+b)* (any string of a and b) must be understood. Regular languages are closed under sum, product, and Kleene star, and all finite languages are regular. The finite automaton is formally defined with states, input letters, and transitions, and can be represented by a transition table or diagram. The example FA shows that language "starting with a" corresponds to the regular expression a(a+b)*.

🧠 Quick Revision Questions

1. Write the regular expression for the EVEN-EVEN language over {a,b}.
2. What is the difference between a*+b* and (a+b)*?
3. When are two regular expressions considered equivalent?
4. If r₁ and r₂ are regular expressions for languages L₁ and L₂, what languages are expressed by r₁+r₂, r₁r₂, and r₁*?
5. In the FA example given, which state is initial and which is final?

📘 Lecture 5 — Theory of Automata

📖 Overview: This lecture explores different notations for transition diagrams and finite automata, focusing on how to design FAs that accept languages with specific patterns such as strings of even length, odd length, strings starting with b, ending in a, not beginning with b, and those beginning and ending with the same letters. Understanding these core patterns is essential for building intuition about how regular languages are recognized by finite automata.

🗂️ Topics Covered

The lecture covers different notations of transition diagrams, including the labeling of initial and final states and the optional naming of states. It then presents several examples of finite automata: one accepting strings of even length, one accepting strings starting with b, one for strings ending in a, one for strings beginning with a, one for strings not beginning with b, and finally one for strings of length two or more beginning and ending in the same letters. The lecture also discusses the important principle that multiple FAs can accept the same language but a given FA accepts only one unique language.

📝 Lecture Summary

Different notations of transition diagrams, languages of strings of even length, Odd length, starting with b, ending in a, beginning with b, not beginning with b, beginning and ending in same letters

It may be noted that to indicate the initial state, an arrow head can also be placed before that state and that the final state is indicated with a double circle, as shown below. It is also to be noted that while expressing an FA by its transition diagram, the labels of states are not necessary.

Example

Σ = {a,b} States: x, y, where x is both initial and final state. Transitions: At state x reading a or b go to state y. At state y reading a or b go to state x.

These transitions can be expressed by the following transition table:

It may be noted that the above transition table may be depicted by the following transition diagram.

The above transition diagram is an FA accepting the language of strings, defined over Σ={a, b} of even length. It may be noted that this language may be expressed by the regular expression ((a+ b) (a + b))*

Example:

Consider the language L of strings, defined over Σ={a, b}, starting with b. The language L may be expressed by RE b(a + b)* , may be accepted by the following FA

Example

Consider the language L of strings, defined over Σ={a, b}, ending in a. The language L may be expressed by RE (a+b)*a.

This language may be accepted by the FA shown aside

There may be another FA corresponding to the given language, as shown aside

Note

It may be noted that corresponding to a given language there may be more than one FA accepting that language, but for a given FA there is a unique language accepted by that FA. It is also to be noted that given the languages L₁ and L₂ ,where L₁ = The language of strings, defined over Σ ={a, b}, beginning with a. L₂ = The language of strings, defined over Σ ={a, b}, not beginning with b The Λ does not belong to L₁ while it does belong to L₂ . This fact may be depicted by the corresponding transition diagrams of L₁ and L₂.

FA₁ Corresponding to L₁ The language L₁ may be expressed by the regular expression a(a + b)*

FA₂ Corresponding to L₂ The language L₂ may be expressed by the regular expression a(a + b)* + Λ

Example

Consider the Language L of Strings of length two or more, defined over Σ = {a, b}, beginning with and ending in same letters. The language L may be expressed by the following regular expression a(a + b)*a + b(a + b)*b It is to be noted that if the condition on the length of string is not imposed in the above language then the strings a and b will then belong to the language.

This language L may be accepted by the FA as shown aside

⭐ Key Takeaways

The most critical points from this lecture are that a finite automaton can be represented without labeling its states, but the initial and final states must always be clearly marked. The language of strings of even length is accepted by a simple two-state FA where the final state is also the initial state. For languages like "ending in a" or "starting with b," the FA must ensure that only strings satisfying the condition reach the final state. A crucial insight is that multiple different FAs can accept the same language, but a given FA defines exactly one unique language. Finally, when defining a language like "beginning and ending with the same letter," the condition on string length (e.g., length two or more) must be carefully considered, as it affects whether single-character strings like "a" and "b" are included.

🧠 Quick Revision Questions

1. What is the regular expression for the language of strings of even length over Σ = {a, b}?
2. In the FA for strings ending in 'a', what happens if the FA is in the final state and reads a 'b'?
3. Why does the empty string Λ belong to the language of strings "not beginning with b" but not to the language of strings "beginning with a"?
4. What is the main difference between the FA for "beginning with a" and the FA for "not beginning with b"?
5. How would you modify the FA for strings beginning and ending with the same letter to also accept the single-character strings "a" and "b"?

📘 Lecture 6 — Theory of Automata

📖 Overview: This lecture explores Finite Automata (FA) for various languages, including strings beginning and ending in different letters, languages accepting all strings or no strings, and languages containing specific patterns like double letters or triple letters. It also introduces the concept of equivalent FAs and the EVEN-EVEN language, demonstrating how regular expressions correspond to FA designs.

🗂️ Topics Covered

The lecture covers examples of FA for languages beginning with and ending in different letters, accepting all strings including Λ, accepting non-empty strings, accepting no strings (empty language), containing double a’s, containing double 0’s or double 1’s, containing triple a’s or triple b’s, and the EVEN-EVEN language. It also discusses equivalent FAs that accept the same language.

📝 Lecture Summary

Example

Consider the Language L of Strings, defined over Σ = {a, b}, beginning with and ending in different letters. The language L may be expressed by the following regular expression a(a + b)*b + b(a + b)*a. This language may be accepted by the following FA with states 1–, 2, 3, 4+, and 5+. The FA has transitions: from 1– on 'a' to 2, from 1– on 'b' to 3; from 2 on 'a' to 2, from 2 on 'b' to 4+; from 3 on 'a' to 5+, from 3 on 'b' to 3; from 4+ on 'a' to 2, from 4+ on 'b' to 4+; from 5+ on 'a' to 5+, from 5+ on 'b' to 3.

Example

Consider the Language L, defined over Σ = {a, b} of all strings including Λ. The language L may be accepted by the following FA with a single state that is both initial and final, with self-loops for 'a' and 'b'. The language L may also be accepted by the following FA with a single initial and final state and self-loops for 'a' and 'b'. The language L may be expressed by the regular expression (a + b)*.

Example

Consider the Language L, defined over Σ = {a, b} of all non empty strings. The language L may be accepted by the following FA with two states: state 1– as initial (non-final) and state 2+ as final, with transitions from 1– on 'a' and 'b' both to 2+, and from 2+ on 'a' and 'b' both to 2+. The above language may be expressed by the regular expression (a + b)+.

Example

Consider the following FA, defined over Σ = {a, b} with a single state 1– that is initial but not final, and a self-loop on 'a' and 'b'. It is to be noted that the above FA does not accept any string, even it does not accept the null string; as there is no path starting from initial state and ending in final state.

Equivalent FAs

It is to be noted that two FAs are said to be equivalent, if they accept the same language, as shown in the following FAs: FA1, FA2, and FA3. Note: FA1 has already been discussed, while in FA2, there is no final state and in FA3, there is a final state but FA3 is disconnected as the states 2 and 3 are disconnected. It may also be noted that the language of strings accepted by FA1, FA2 and FA3 is denoted by the empty set i.e. { } OR Ø.

🔑 Definition — Equivalent FAs: Two FAs are said to be equivalent if they accept the same language.

Example

Consider the Language L of strings, defined over Σ = {a, b}, containing double a. The language L may be expressed by the regular expression (a+b)(aa)(a+b). This language may be accepted by the following FA with states: 1–, 2, 3+. The FA has transitions: from 1– on 'a' to 2, from 1– on 'b' to 1–; from 2 on 'a' to 3+, from 2 on 'b' to 1–; from 3+ on 'a' to 3+, from 3+ on 'b' to 3+.

💡 Why this matters: This FA remembers if it has seen one 'a' (state 2) and then accepts once a second 'a' appears (state 3+).

Example

Consider the language L of strings, defined over Σ={0, 1}, having double 0’s or double 1’s. The language L may be expressed by the regular expression (0+1)(00 + 11)(0+1). This language may be accepted by the following FA with states: – (initial), x, y, and + (final). The FA has transitions: from – on '0' to x, from – on '1' to y; from x on '0' to +, from x on '1' to y; from y on '0' to x, from y on '1' to +; from + on '0' and '1' both back to +.

Example

Consider the language L of strings, defined over Σ={a, b}, having triple a’s or triple b’s. The language L may be expressed by RE (a+b)(aaa + bbb)(a+b). This language may be accepted by the FA with states: 1–, 2, 3, 4, 5, and 6+. The FA has transitions: from 1– on 'a' to 2, from 1– on 'b' to 3; from 2 on 'a' to 4, from 2 on 'b' to 3; from 3 on 'a' to 2, from 3 on 'b' to 5; from 4 on 'a' to 6+, from 4 on 'b' to 3; from 5 on 'a' to 2, from 5 on 'b' to 6+; from 6+ on 'a' to 6+, from 6+ on 'b' to 6+.

Example

Consider the EVEN-EVEN language, defined over Σ = {a, b}. As discussed earlier that EVEN-EVEN language can be expressed by the regular expression (aa+bb+(ab+ba)(aa+bb)(ab+ba)). EVEN-EVEN language may be accepted by the FA with states: 1±, 2, 3, and 4. The FA has transitions: from 1± on 'a' to 2, from 1± on 'b' to 3; from 2 on 'a' to 1±, from 2 on 'b' to 4; from 3 on 'a' to 4, from 3 on 'b' to 1±; from 4 on 'a' to 3, from 4 on 'b' to 2.

🔑 Definition — EVEN-EVEN language: The language of strings over Σ={a,b} where the number of 'a's is even and the number of 'b's is even.

⭐ Key Takeaways

Students must remember that FAs can be designed for various languages by creating states that track the necessary "memory" of the input seen so far. A language accepting all strings (including Λ) uses a single accepting state, while the language of non-empty strings requires the initial state to be non-final. Equivalent FAs accept the same language, and the FA with no path to a final state accepts the empty language. For pattern languages like double or triple letters, states are used to count consecutive occurrences until the pattern is found, after which all subsequent inputs lead to a final trap state.

🧠 Quick Revision Questions

1. What regular expression represents the language of strings beginning with and ending in different letters over {a,b}?
2. How many states are needed in an FA to accept all strings including the null string?
3. What does it mean for two FAs to be equivalent?
4. Describe the state transitions for an FA that accepts strings containing "aa" over {a,b}.
5. How many states are in the FA for the EVEN-EVEN language, and what do they represent?

📘 Lecture 7 — FA Corresponding to Finite Languages, Transition Graphs

📖 Overview: This lecture demonstrates methods for constructing Finite Automata that accept finite languages, using both a direct state-transition approach and a tree structure method. It also introduces Transition Graphs (TGs) as a more generalized model that allows transitions on substrings including the null string. Understanding these constructions is fundamental for building automata from regular expressions and finite language specifications.

🗂️ Topics Covered

The lecture covers building FA for finite languages using the tree method and direct state labeling, with multiple examples including languages with specific ending conditions. It concludes with the formal definition and properties of Transition Graphs (TGs) , which extend FA by permitting transitions on arbitrary substrings.

📝 Lecture Summary

FA corresponding to finite languages

The lecture begins by showing how to construct an FA for the finite language L = {Λ, b, ab, bb} over Σ = {a, b}, expressed as Λ + b + ab + bb. The FA is built with states that include Dead States (also called Waste Baskets or Davey John Lockers), which are states that once entered cannot be exited. The FA includes a start state (1±), final states (2+, 4+, 5+), and dead states (x, y) to handle all possible transitions.

🔑 Definition — Dead State: A state from which there is no possible transition to any other state; once entered, the automaton can never leave it. 📌 Example: In the FA for L = {Λ, b, ab, bb}, state x and state y are dead states. If the input string contains an 'a' from state 2 or a 'b' from state 3, the automaton goes to a dead state and will never reach a final state.

💡 Why this matters: Dead states are essential for building complete FA that process all possible input strings, ensuring the automaton is deterministic and well-defined for every input.

Tree Structure Method for Building FA

The tree structure method is introduced as an alternative approach for constructing FA, especially useful for languages with a small number of strings. For the language L = {Λ, b, ab, bb}, a tree is built starting from the start state (1±), with branches for each possible string. Each complete string ends at a final state, and additional dead state transitions are added to handle all other input possibilities.

📌 Example: The tree for L = {Λ, b, ab, bb} starts at state 1±. From there:

• On Λ (empty string): state 1 is already final
• On 'b': go to state 2+ (final)
• On 'a' then 'b': go from 1 to 3 to 4+ (final)
• On 'b' then 'b': go from 1 to 2 to 5+ (final) All other transitions (e.g., a from 2, a from 4, a from 5, b from 3, etc.) go to dead states (6, 7, 8, x).

Example: Language L = {aa, bab, aabb, bbba}

This language over Σ = {a, b} is expressed as aa + bab + aabb + bbba. The corresponding FA is built with multiple paths: from start state 1–, going to state 2 on 'a', then to state 3+ on 'a' (final). For 'bab', the path is 1– → 4 → 5 → 6+. For 'aabb': 1– → 2 → 7 → 8 → 9+. For 'bbba': 1– → 10 → 6 → 11+ → y (final). All other transitions go to dead state y.

📌 Example: String "aa" is accepted: start at 1–, read 'a' → go to 2, read 'a' → go to 3+ (final state). String "aab" is rejected: start at 1–, read 'a' → 2, read 'a' → 7 (waiting state for "aabb"), read 'b' → all transitions from 7 on 'b' go to dead state y, so rejected.

Example: Language L = {w ∈ {a,b}* : length(w) ≥ 2 and w neither ends in aa nor bb}

This language is expressed by the regular expression (a+b)*(ab+ba). The FA is built using a technique from J.C. Martin's book, where states are labeled according to the last one or two letters read: Λ (start), aa, ab, ba, bb. The accepting states are those whose labels end in "ab" or "ba".

🔑 Definition — State Labeling: States are labeled by the last one or two characters of the string read so far, allowing the automaton to "remember" the necessary suffix to decide acceptance.

📌 Example: For the string "bab":

• Start at Λ, read 'b' → go to state labeled "b" (not explicitly shown but transitions go to appropriate two-letter states)
• Read 'a' → go to state "ba"
• Read 'b' → go to state "ab" (final state, since it ends in "ab") The FA ensures that only strings of length ≥ 2 ending in "ab" or "ba" are accepted.

Example: Language L = {w ∈ {a,b}* : w does not end in aa}

This language is expressed by the regular expression Λ + a + b + (a+b)*(ab+ba+bb). The FA uses the same state labeling technique (Λ, aa, ab, ba, bb), with final states being all except "aa" (and the empty string is accepted via Λ as a final state).

📌 Example: String "aba": start at Λ, read 'a' → go to some state, read 'b' → go to "ab", read 'a' → go to "ba" (final, since it ends in "ba"). String "baa": start Λ, read 'b' → go to "b" state, read 'a' → go to "ba", read 'a' → go to "aa" (non-final, rejected because it ends in "aa").

Method 5: Transition Graph (TG)

Transition Graphs (TGs) are introduced as a generalization of FA. A TG consists of:

• Finite number of states, at least one start state and some (maybe none) final states
• Finite set of input letters (Σ)
• Finite set of transitions that allow moving from one state to another based on reading specified substrings of input letters, possibly including the null string (Λ)

🔑 Definition — Transition Graph (TG): A collection of states with transitions labeled by substrings (not just single letters) of the input alphabet, including the possibility of Λ-transitions.

📌 Example: In a TG, a transition from state A to state B could be labeled "ab" meaning the entire substring "ab" is consumed in one step. An edge labeled Λ means the machine can move without consuming any input.

⭐ Key Takeaways

The most critical concepts to remember from this lecture are: Dead states are essential for making FA complete and deterministic, trapping invalid inputs permanently. The tree structure method provides a systematic way to build FA for finite languages by constructing paths for each string and adding dead states for all other transitions. The state labeling technique (labeling states by the last characters read) is powerful for constructing FA that recognize languages based on string endings, such as "strings not ending in aa". Transition Graphs (TGs) generalize FA by allowing transitions on arbitrary substrings (including Λ), making them more flexible but still equivalent in power to FA. Finally, a language's regular expression directly guides the construction of its corresponding FA or TG.

🧠 Quick Revision Questions

1. What is a dead state and why is it necessary in constructing FA for finite languages?
2. For the language L = {aa, bab, aabb, bbba}, using the tree method, what path does the string "bab" follow from the start state?
3. How does the state labeling technique help construct an FA for the language of strings that do NOT end in "aa"?
4. What is the key difference between a Transition Graph (TG) and a standard Finite Automaton (FA) regarding transition labels?
5. If a language is expressed by the regular expression (a+b)*(ab+ba), what are the final state labels in the corresponding FA built using the Martin technique?

📘 Lecture 8 — Examples of TGs: accepting all strings, accepting none, starting with b, not ending in b, containing aa, containing aa or bb

📖 Overview: This lecture introduces Transition Graphs (TGs) as a more general model than Finite Automata (FA). It demonstrates through multiple examples how TGs can be constructed to accept specific languages, including the empty language, and explains the crucial relationship that every FA is a TG, but not every TG is an FA.

🗂️ Topics Covered

The lecture covers the definition of a TG's acceptance criteria (at least one path from initial to final state), examples of TGs accepting different languages (all strings including Λ, empty language, strings starting with b, strings not ending in b, strings containing aa, strings containing aa or bb), and the relationship between TGs and FAs.

📝 Lecture Summary

Note

It is to be noted that in TG there may exist more than one paths for a certain string, while there may not exist any path for a certain string as well. If there exists at least one path for a certain string, starting from initial state and ending in a final state, the string is supposed to be accepted by the TG, otherwise the string is supposed to be rejected. Obviously collection of accepted strings is the language accepted by the TG.

Example

Consider the Language L , defined over Σ = {a, b} of all strings including Λ. The language L may be accepted by the following TG

TG₁: a,b a,b

The language L may also be accepted by the following TG

TG₂: a,b

💡 Why this matters: A TG that accepts all strings, including the empty string Λ, can be as simple as a single initial-final state with a loop for all alphabet letters.

Example

Consider the following TGs

TG₁:

TG₂:

TG₃: a,b

It may be observed that in the first TG, no transition has been shown. Hence this TG does not accept any string, defined over any alphabet. In TG₂ there are transitions for a and b at initial state but there is no transition at state 1. This TG still does not accept any string. In TG₃ there are transitions at both initial state and state 1, but it does not accept any string.

Thus none of TG₁, TG₂ and TG₃ accepts any string, i.e. these TGs accept empty language. It may be noted that TG₁ and TG₂ are TGs but not FA, while TG₃ is both TG and FA as well.

It may be noted that every FA is a TG as well, but the converse may not be true, i.e. every TG may not be an FA.

Example

Consider the language L of strings, defined over Σ={a, b}, starting with b. The language L may be expressed by RE b(a + b)* , may be accepted by the following TG

a,b

Example

Consider the language L of strings, defined over Σ={a, b}, not ending in b. The language L may be expressed by RE Λ + (a + b) a* , may be accepted by the following TG

a,b

Example

Consider the Language L of strings, defined over Σ = {a, b}, containing double a. The language L may be expressed by the following regular expression (a+b) (aa) (a+b)** . This language may be accepted by the following TG

Example

Consider the language L of strings, defined over Σ={a, b}, having double a or double b. The language L can be expressed by RE (a+b) (aa + bb) (a+b)** .

The above language may also be expressed by the following TGs.

OR

OR

Note

In the above TG if the states are not labeled then it may not be considered to be a single TG.

⭐ Key Takeaways

A string is accepted by a TG if there exists at least one path from the initial state to a final state labeled with that string; the existence of other paths that reject the string is irrelevant. Not every TG is a Finite Automaton (FA), but every FA is a TG because TGs are a more general model allowing multiple paths and undefined transitions. A TG with no transitions or with transitions that never lead to a final state accepts the empty language. Different TGs (with different numbers of states and transition structures) can accept the same language, demonstrating the non-uniqueness of TGs for a given regular language.

🧠 Quick Revision Questions

1. What is the acceptance criterion for a string in a Transition Graph (TG)?
2. Can a TG accept the empty language? If so, give an example.
3. Is it true that every TG is also a Finite Automaton (FA)? Justify your answer.
4. Construct a TG that accepts the language of all strings over {a, b} that start with 'b'.
5. How many different TGs can accept the same regular language?

📘 Lecture 9 — Theory of Automata (CS402) — Lecture N0. 9

📖 Overview: This lecture focuses on constructing Transition Graphs (TGs) for specific languages defined by regular expressions. It demonstrates how to design TGs for languages containing substrings, having specific start/end conditions, and even clump constraints. The lecture concludes by introducing the Generalized Transition Graph (GTG), a more powerful model where edges are labeled with regular expressions instead of single letters.

🗂️ Topics Covered

Examples of TGs accepting languages: containing "aaa" or "bbb", beginning and ending in different letters, beginning and ending in same letters, EVEN-EVEN language, strings where a’s occur in even clumps and end with three or more b’s. An example showing different paths traced by one string through a TG. The definition and concept of Generalized Transition Graphs (GTGs).

📝 Lecture Summary

Example (TG for language containing "aaa" or "bbb")

Consider the language L of strings, defined over Σ = {a, b}, having triple a or triple b. The language L may be expressed by RE (a+b)* (aaa + bbb) (a+b)*. This language may be accepted by the following TG.

• Diagram 1 (First TG design): A single start state (-) connected to a single final state (+) by an edge labeled aaa, bbb. This means the string must contain either "aaa" or "bbb".
• Diagram 2 (More detailed TG design): A start state (1-) that loops on a,b before going to state (2+) on reading aaa or bbb. State (2+) then loops on a,b. This shows that the required substring can appear anywhere in the string.

Example (TG for strings beginning and ending in different letters)

Consider the language L of strings, defined over Σ = {a, b}, beginning and ending in different letters. The language L may be expressed by RE a(a + b)* b + b(a + b)* a. The language L may be accepted by the following TG.

• Diagram: A start state (1-) has two outgoing edges: one labeled a going to state (2), and one labeled b going to state (3). State (2) has a loop on a,b and an edge labeled b to the final state (4+). State (3) has a loop on a,b and an edge labeled a to the final state (5+). This enforces the first and last letters to be different.

Example (TG for strings beginning and ending in same letters)

Consider the Language L of strings of length two or more, defined over Σ = {a, b}, beginning with and ending in same letters. The language L may be expressed by the following regular expression a(a + b)* a + b(a + b)* b. This language may be accepted by the following TG.

• Diagram: A start state (-) has an edge labeled a that goes to a middle state, and an edge labeled b that goes to a different middle state. Each middle state has a loop on a,b. The first middle state leads to a final state (+) on reading a, and the second middle state leads to the final state (+) on reading b. This ensures the string starts and ends with the same letter.

Example (TG for the EVEN-EVEN language)

Consider the EVEN-EVEN language, defined over Σ = {a, b}. As discussed earlier, the EVEN-EVEN language can be expressed by a regular expression (aa+bb+(ab+ba)(aa+bb)*(ab+ba))*. The language EVEN-EVEN may be accepted by the following TG.

• Diagram: A 4-state TG where the start state (-) is also the final state (+). State (1) has a loop on aa and bb. State (2) has a loop on aa and bb and is connected to states (3) and (4) via ab and ba. This is a compact representation of the EVEN-EVEN language.

Example (TG for strings with a's in even clumps ending in three or more b's)

Consider the language L, defined over Σ={a, b}, in which a’s occur only in even clumps and that ends in three or more b’s. The language L can be expressed by its regular expression (aa)* b(b*+(aa(aa)*b)*) bb OR (aa)* b(b*+ ((aa)+b)*) bb. The language L may be accepted by the following TG.

• Diagram: A start state (-) has a loop on aa. From there, an edge labeled b goes to state (1). State (1) loops on bb and has an edge labeled b to state (2). State (2) has an edge labeled b to the final state (+), which loops on aa. State (1) also has an edge labeled ab to state (3), which has a loop on aa and an edge labeled b back to state (1).

Example (Different paths traced by one string)

Consider the following TG (a 5-state TG with states -, 1, 2, 3, 4, and +).

Diagram Description:

• Start state (-) has an edge labeled a to state (4).
• State (4) has edges: ab to state (3), b to state (+), and a loop on b.
• Final state (+) has edges: bb and a to state (2), and ab and b to state (3).
• State (2) has edges: bb to state (1), a to state (+).
• State (1) has an edge aa to state (+).
• State (3) has an edge bb to state (2).

Consider the string abbbabbbabba. It may be observed that the above string traces the following three paths (using the states):

1. (a) (b) (b) (b) (ab) (bb) (a) (bb) (a) → Path: (-) → (4) → (4) → (+) → (+) → (3) → (2) → (2) → (1) → (+)
2. (a) (b) ((b)(b)) (ab) (bb) (a) (bb) (a) → Path: (-) → (4) → (+) → (+) → (+) → (3) → (2) → (2) → (1) → (+)
3. (a) ((b) (b)) (b) (ab) (bb) (a) (bb) (a) → Path: (-) → (4) → (4) → (4) → (+) → (3) → (2) → (2) → (1) → (+)

Which shows that all these paths are successful (i.e., the path starting from an initial state and ending in a final state). Hence the string abbbabbbabba is accepted by the given TG.

💡 Why this matters: This example demonstrates that a single string can have multiple successful paths through a TG. This is a key property of nondeterminism in finite automata.

Generalized Transition Graphs (GTGs)

A generalized transition graph (GTG) is a collection of three things:

1. Finite number of states, at least one of which is start state and some (maybe none) final states.
2. Finite set of input letters (Σ) from which input strings are formed.
3. Directed edges connecting some pair of states labeled with regular expression.

It may be noted that in GTG, the labels of transition edges are corresponding regular expressions.

🔑 Definition — Generalized Transition Graph (GTG): A graph consisting of a finite number of states (with at least one start state and some final states), a finite input alphabet Σ, and directed edges labeled with regular expressions over Σ.

⭐ Key Takeaways

In this lecture, you learned how to construct Transition Graphs (TGs) from specific regular expressions by mapping language constraints directly onto state transitions. The critical feature is that a single input string can have multiple successful paths through a nondeterministic TG, as demonstrated by the string abbbabbbabba. Finally, the Generalized Transition Graph (GTG) was introduced as a more powerful model where edges are labeled with entire regular expressions, not just single symbols, which will be essential for converting regular expressions into finite automata.

🧠 Quick Revision Questions

1. How would you design a TG that accepts strings containing "aba" where the substring must appear exactly once?
2. For the TG in the "different paths" example, can you find a string that has more than three successful paths?
3. What is the formal difference between a standard TG and a Generalized Transition Graph (GTG)?
4. Can a TG have a loop on a state that represents a complex regular expression?
5. If a string has both a successful and an unsuccessful path in a TG, is the string accepted or rejected?

📘 Lecture 10 — Examples of GTGs, Nondeterminism, Kleene’s Theorem

📖 Overview: This lecture demonstrates how Generalized Transition Graphs (GTGs) can accept various languages defined by regular expressions. It also introduces the concept of nondeterminism and presents Kleene’s Theorem, which establishes the equivalence of Finite Automata, Transition Graphs, and Regular Expressions.

🗂️ Topics Covered

The lecture covers examples of GTGs accepting languages containing double letters (aa or bb), strings beginning and ending with the same letter, strings beginning and ending with different letters, and strings containing triple letters (aaa or bbb). It also explains nondeterminism in TGs and GTGs, states Kleene’s Theorem with its three parts, and provides the proof for Part I.

📝 Lecture Summary

Example — Language containing aa or bb

Consider the language L of strings, defined over Σ = {a,b}, containing double a or double b. The language L can be expressed by the following regular expression (a+b)* (aa + bb) (a+b)*. The language L may be accepted by the following GTG with a start state (-) leading to a + state via edges labeled a+b, and the + state having a loop of a+b and an edge back to the start labeled aa+bb.

Example — Language beginning with and ending in same letters

Consider the Language L of strings, defined over Σ = {a, b}, beginning with and ending in same letters. The language L may be expressed by the following regular expression (a+b)+ a(a + b)*a + b(a + b)*b. This language may be accepted by the following GTG with a start state (-) that has edges labeled a+ and b+ leading to the final state (+), along with additional paths for a(a+b)*a and b(a+b)*b.

Example — Language beginning and ending in different letters

Consider the language L of strings, defined over Σ = {a, b}, beginning and ending in different letters. The language L may be expressed by RE a(a + b)*b + b(a + b)*a. The language L may be accepted by the following GTG with edges labeled a(a+b)*b and b(a+b)*a between the start state (-) and final state (+). The language L may be accepted by the following GTG as well with alternative paths.

Example — Language having triple a or triple b

Consider the language L of strings, defined over Σ = {a, b}, having triple a or triple b. The language L may be expressed by RE (a+b)* (aaa + bbb) (a+b)*. This language may be accepted by the following GTG with a start state (-) having an edge labeled (a+b)*(aaa+bbb)(a+b)* to the final state (+). OR with a start state (-) having an edge labeled a+b to a + state which has a loop of a+b and an edge back to start labeled aaa+bbb.

Nondeterminism

TGs and GTGs provide certain relaxations i.e. there may exist more than one path for a certain string or there may not be any path for a certain string, this property creates nondeterminism and it can also help in differentiating TGs or GTGs from FAs. Hence an FA is also called a Deterministic Finite Automaton (DFA).

🔑 Definition — Nondeterminism: The property of a computational model where, for a given input, there may be multiple possible paths or no path at all, as opposed to deterministic models where each input leads to exactly one state.

Kleene’s Theorem

If a language can be expressed by FA or TG or RE then it can also be expressed by the other two as well. It may be noted that the theorem is proved by proving the following three parts:

Kleene’s Theorem Part I — If a language can be accepted by an FA then it can be accepted by a TG as well.

Kleene’s Theorem Part II — If a language can be accepted by a TG then it can be expressed by an RE as well.

Kleene’s Theorem Part III — If a language can be expressed by a RE then it can be accepted by an FA as well.

Proof (Kleene’s Theorem Part I)

Since every FA can be considered to be a TG as well, therefore there is nothing to prove.

💡 Why this matters: Kleene’s Theorem is the foundational result of automata theory, proving that all three models (FA, TG, RE) are equivalent in expressive power. This means we can freely convert between models to leverage the strengths of each for different tasks.

⭐ Key Takeaways

Kleene’s Theorem establishes that Finite Automata, Transition Graphs, and Regular Expressions are all equivalent in the languages they can represent. GTGs provide flexibility through nondeterminism, allowing multiple paths or no path for a string, which distinguishes them from deterministic FAs. The proof of Part I is trivial because every FA is inherently a TG. Regular expressions can be directly transformed into GTGs by placing the entire RE on a single edge between start and final states. The ability to represent languages with double letters, same/different beginning and ending letters, and triple letters demonstrates the practical application of GTGs.

🧠 Quick Revision Questions

1. What are the three equivalent representations of regular languages according to Kleene’s Theorem?
2. How is nondeterminism exhibited in TGs and GTGs but not in FAs?
3. Why is the proof of Kleene’s Theorem Part I considered trivial?
4. How would you construct a GTG for the language containing the substring "aba"?
5. What is the relationship between a DFA and a TG, and why is a DFA considered a special case?

📘 Lecture 11 — Proof of Kleene’s Theorem Part II, Examples of TGs to REs

📖 Overview: This lecture presents the complete proof of Kleene’s theorem Part II by providing an algorithm that converts any Transition Graph (TG) into a Regular Expression (RE). It explains four systematic steps to transform a TG into a Generalized Transition Graph (GTG) with a single initial state connected to a single final state by one transition edge, whose label becomes the desired RE. Multiple examples illustrate each step and the overall conversion process.

🗂️ Topics Covered

The lecture covers the proof of Kleene’s theorem Part II using a step-by-step algorithm, including handling multiple start states, multiple final states, merging parallel transitions, and eliminating states through bypassing. It also demonstrates the conversion of TGs to REs through worked examples, including handling circuits at states and sequential state elimination.

📝 Lecture Summary

Proof (Kleene’s Theorem Part II)

To prove part II of the theorem, an algorithm consisting of different steps is explained showing how a Regular Expression (RE) can be obtained corresponding to a given Transition Graph (TG). For this purpose, the notion of TG is changed to that of Generalized Transition Graph (GTG) — where the labels of transitions are corresponding REs.

🔑 GTG (Generalized Transition Graph): A TG where transition labels are REs instead of single letters.

💡 Why this matters: This algorithm provides a mechanical method to find the language (as an RE) accepted by any TG, which is essential for automata theory proofs and practical pattern matching.

Step 1: Handling Multiple Start States

If a TG has more than one start states, then introduce a new start state connecting the new state to the old start states by transitions labeled by Λ and make the old start states the non-start states.

📌 Example: Given a TG with start state 1- and start state 2-, this step introduces a new start state (minus sign) connected to both states 1 and 2 by Λ transitions, and states 1 and 2 become non-start states.

Step 2: Handling Multiple Final States

If a TG has more than one final states, then introduce a new final state, connecting the old final states to the new final state by transitions labeled by Λ.

📌 Example (continuing from Step 1): Given a TG with final states 3+ and 4+, this step introduces a new final state (plus sign) connected from both states 3 and 4 by Λ transitions, and states 3 and 4 become non-final states.

Step 3: Merging Parallel Transitions

If a state has two (or more than one) incoming transition edges labeled by the corresponding REs, from the same state (including the possibility of loops at a state), then replace all these transition edges with a single transition edge labeled by the sum of corresponding REs.

🔑 Sum of REs: The RE formed by adding the individual REs with a plus (+) sign, representing alternation (union).

📌 Example: If state 3 has two incoming transitions from state 5 — one labeled r1 and another labeled r2 — these are replaced by a single transition labeled r1 + r2.

Generalization: For any finite number of transitions from the same source to the same target (including self-loops), all are replaced by a single transition labeled with the sum of all their REs.

Step 4: Bypass and State Elimination

If three states in a TG are connected in sequence, then eliminate the middle state and connect the first state with the third by a single transition (include the possibility of circuit as well) labeled by the RE which is the concatenation of corresponding two REs in the existing sequence.

🔑 Concatenation of REs: The RE formed by writing one RE followed by another, representing sequential composition.

📌 Example (simple): Given states 1 → 2 (labeled r1) and 2 → 3 (labeled r2), eliminating state 2 gives a direct transition from 1 to 3 labeled r1 r2.

📌 Example (with circuit at middle state): Given state 1 → 3 (labeled r1), state 3 has a self-loop (labeled r3), and state 3 → 5 (labeled r2). To eliminate state 3, connect state 1 to state 5 with label r1 (r3)* r2.

Formula for circuit elimination: r1 (r3)* r2

• r1 = path from first state to the state being eliminated
• r3 = loop (circuit) at the state being eliminated
• r2 = path from the eliminated state to the next state

Example — Complete TG to RE Conversion

Starting TG: A TG with start state 1-, final state 4+, and intermediate states 2, 3 with various transitions.

Step 1: Already has single start state (already processed).

Step 2: Introduce new final state +. Connect old final state 4 to new final state + with Λ transition.

Step 3: (Applied during elimination process)

Step 4:

• Eliminate state 2 and state 3 (sequence elimination)
• Eliminate state 1 (final reduction)

Final Result: The TG is reduced to a single transition from start state to final state labeled: (ab + ba)(aa + b)*(aaa + bba)

Thus the required RE = (ab + ba)(aa + b)*(aaa + bba)

⭐ Key Takeaways

The core algorithm for converting any TG to an RE involves four steps: (1) adding a new start state with Λ transitions to all old start states; (2) adding a new final state with Λ transitions from all old final states; (3) merging parallel edges from the same source to the same destination by summing their REs; and (4) eliminating intermediate states sequentially using the bypass rule r1(r3)*r2 when a circuit exists at the eliminated state. The final result is a GTG with one start state and one final state connected by a single transition whose label is the desired RE. This algorithm provides a constructive proof of Kleene’s theorem Part II — that every TG corresponds to some RE.

🧠 Quick Revision Questions

1. What is the purpose of introducing a new start state in Step 1 of the algorithm?
2. How do you handle multiple final states when converting a TG to an RE?
3. What rule is used to replace multiple transition edges from the same source to the same target state?
4. Write the formula for eliminating a state that has a circuit (loop), with incoming path r1 and outgoing path r2.
5. What is the RE obtained for the example TG discussed at the end of the lecture?

📘 Lecture 12 — Examples of Writing REs to TGs, RE Corresponding to TG Accepting EVEN-EVEN Language, Kleene’s Theorem Part III (Method 1: Union of FAs), Examples of FAs Corresponding to Simple REs, Example of Kleene’s Theorem Part III (Method 1) Continued

📖 Overview: This lecture demonstrates how to convert Transition Graphs (TGs) into Regular Expressions (REs) through state elimination and reduction techniques, including a detailed example for the EVEN-EVEN language. It introduces Kleene’s Theorem Part III, which states that for every regular expression, there exists a Finite Automaton (FA), and explains Method 1 for constructing an FA corresponding to the union of two regular expressions using their respective FAs.

🗂️ Topics Covered

The lecture begins with a detailed example of converting a TG to an RE by reducing it to a single initial and single final state with a single transition edge, obtaining the RE (b+aa)b*+(a+bb)a*. It then covers converting a TG for the EVEN-EVEN language into the RE (aa+bb+(ab+ba)(aa+bb)*(ab+ba))*. The lecture states Kleene’s Theorem Part III and provides simple examples of FAs for single-letter languages. Finally, it explains Method 1 (Union of FAs) in detail, constructing an FA for the union of two regular expressions r₁ = (a+b)*b and r₂ = (a+b)*aa(a+b)*, resulting in a five-state FA and the combined RE.

📝 Lecture Summary

Example

The lecture begins with a TG that is first reduced by adding a single initial state (connected to the original initial state via a Λ edge) and a single final state (connected from the original final state via a Λ edge). The TG is then simplified step-by-step by eliminating states and combining transition edges using bypass and concatenation rules.

🔑 Definition — Elimination of a state: To eliminate a state, a new path (edge) is created directly from its predecessor to its successor, labeled with the concatenation of the incoming edge, the loop on the state (if any), and the outgoing edge.

📐 Formula: Edge from A to C = (Edge(A→B)) (Loop on B)* (Edge(B→C))

📌 Example: To eliminate state 1 from a TG, the path from the initial state to the state after 1 (e.g., state 3) is replaced by a single edge labeled with the concatenation of the edge from the start to state 1 and the edge from state 1 to state 3, considering any loops on state 1. Through multiple such reductions, the TG is ultimately transformed into a single edge from the initial to the final state, labeled with the RE (b+aa)b*+(a+bb)a* .

Example (EVEN-EVEN Language)

This example starts with a TG that accepts the EVEN-EVEN language (strings with an even number of a's and an even number of b's). The initial state is also a final state. To prepare for state elimination, an additional initial state and an additional final state are introduced, connected to the original state via Λ edges.

🔑 Definition — EVEN-EVEN language: The language of all strings over Σ = {a, b} where the total number of a's is even and the total number of b's is even.

📌 Example: The TG has two states. State 2 (the original state) is eliminated by applying the formula. The resulting TG has a single state (state 1) with a complex loop. The loop labels are simplified using algebraic laws of regular expressions (like (aa+bb)+ (ab+ba)(aa+bb)*(ab+ba)). After eliminating the final state 1, the resulting RE is (aa+bb+(ab+ba)(aa+bb)*(ab+ba))* .

💡 Why this matters: This RE is the canonical regular expression for the EVEN-EVEN language, a classic example in automata theory.

Kleene’s Theorem Part III

Statement: If the language can be expressed by a RE then there exists an FA accepting the language.

🔑 Definition — Kleene’s Theorem Part III: This is the converse of Part I and Part II. It ensures that any regular expression is computationally realizable by a deterministic finite automaton.

📌 Example 1: For the language defined over Σ = {a,b} consisting of only the single letter b , the FA has an initial state (x₁) that transitions to a final state (x₂) on reading 'b'. On reading 'a', it stays in x₁. x₂ is a dead state (or final state with a self-loop on a and b).

📌 Example 2: For the language consisting of only the null string Λ, the FA has a single state which is both initial and final. This state has no transitions.

Method1 (Union of two FAs)

This method builds an FA for the union (r₁ + r₂) by combining the FAs of r₁ and r₂. The new FA's states represent pairs of states from the two original FAs.

🔑 Definition — Product construction (Union): The union FA, FA₃, has states that are ordered pairs (zᵢ ≡ (xⱼ, yₖ)), where xⱼ is a state from FA₁ and yₖ is a state from FA₂. The start state is the pair of start states (x₁, y₁). A state in FA₃ is final if either its x-component is final in FA₁ or its y-component is final in FA₂ (or both).

📐 Formula: Transition ([x₁, y₁], a) = [Transition(FA₁, x₁, a), Transition(FA₂, y₁, a)]

📌 Example: Let r₁ = (a+b)*b (FA₁: starts at x₁, ends at x₂ on 'b') and r₂ = (a+b)*aa(a+b)* (FA₂: starts at y₁, ends at y₃ on 'aa'). The union FA (FA₃) is constructed.

• State z₁ = (x₁, y₁) → on 'a': (x₁, y₂) = z₂; on 'b': (x₂, y₁) = z₃
• State z₂ = (x₁, y₂) → on 'a': (x₁, y₃) = z₄; on 'b': (x₂, y₁) = z₃
• State z₃⁺ = (x₂, y₁) → on 'a': (x₁, y₂) = z₂; on 'b': (x₂, y₁) = z₃
• State z₄⁺ = (x₁, y₃) → on 'a': (x₁, y₃) = z₄; on 'b': (x₂, y₃) = z₅
• State z₅⁺ = (x₂, y₃) → on 'a': (x₁, y₃) = z₄; on 'b': (x₂, y₃) = z₅ The states z₃, z₄, z₅ are final because either x₂ or y₃ is final. The RE corresponding to this new FA is (a+b)*b + (a+b)*aa(a+b)* .

⭐ Key Takeaways

• The state elimination method for converting a TG to an RE involves introducing single initial/final states and systematically removing internal states by bypassing them with new edges labeled with the concatenation of surrounding paths, using the Kleene star for loops.
• The EVEN-EVEN language has a concise regular expression: (aa+bb+(ab+ba)(aa+bb)*(ab+ba))*, which is derived from its corresponding TG.
• Kleene’s Theorem Part III proves the completeness of regular expressions: every regular expression can be realized by a finite automaton, forming a closed system.
• Method 1 (Union of FAs) is a practical construction where the states of the union FA are all possible pairs of states from the two component FAs.
• A state in the union FA is final if and only if at least one of its component states is final, which correctly accepts strings from either language.

🧠 Quick Revision Questions

1. What is the final regular expression obtained from the first example TG (not the EVEN-EVEN one)?
2. What is the regular expression for the EVEN-EVEN language as derived in this lecture?
3. State Kleene’s Theorem Part III in your own words.
4. In the union (product) construction for two FAs, how is a state of the combined FA determined to be a final state?
5. For the union of r₁ = (a+b)*b and r₂ = (a+b)*aa(a+b)*, what are the final states in the resulting FA?

📘 Lecture 13 — Theory of Automata (CS402)

📖 Overview: This lecture continues the study of Kleene’s theorem, specifically Part III, which shows how to build a Finite Automaton (FA) for a given regular expression. It covers Method 1 (building an FA for union of regular expressions) with more examples, and introduces Method 2 for building an FA for the concatenation of two regular expressions. Understanding these methods is crucial for proving that all regular languages can be represented by FAs.

🗂️ Topics Covered

The lecture begins by reviewing an example of Kleene’s theorem part III (method 1) for union, noting the reduction in states from six to five. It then provides a complete example of building an FA for the union of two regular expressions, r₁ = (a+b)a and r₂ = (a+b)((a+b)(a+b)) or ((a+b)(a+b))(a+b), followed by another example for r₁ = ((a+b)(a+b)) and r₂ = (a+b)((a+b)(a+b)) or ((a+b)(a+b))(a+b)*. The main body introduces Method 2 (Concatenation of two FAs) and works through a detailed example for *r₁ = (a+b)b and *r₂ = (a+b)*aa(a+b)**.

📝 Lecture Summary

Examples of Kleene’s theorem part III (method 1) continued

This section continues the method for constructing an FA corresponding to the union (+) of two regular expressions, r₁ and r₂. The resulting FA, FA₃, accepts a string if it is accepted by FA₁ or by FA₂. The construction uses a transition table where each new state in FA₃ is a pair (xᵢ, yⱼ), representing a possible combination of a state from FA₁ and a state from FA₂. The initial state is (x₁, y₁). A state is a final state if either of its component states (xᵢ or yⱼ) is a final state in its respective FA. The transition for a letter is found by applying that letter to both component states.

It may be noted that the example discussed at the end of previous lecture, FA₁ contains two states while FA₂ contains three states. Hence the total number of possible combinations of states of FA₁ and FA₂, in sequence, will be six. For each combination the transitions for both a and b can be determined, but using the method in the example, number of states of FA₃ was reduced to five.

Example Let r₁ = (a+b)a and the corresponding FA₁ be: [FA₁ diagram with two states, x₁ and x₂, where x₁ has a loop on b to itself and a transition on a to x₂, and x₂ is a final state]. Also r₂ = (a+b)((a+b)(a+b)) or ((a+b)(a+b))(a+b)* and FA₂ be: [FA₂ diagram with two states, y₁ and y₂, where y₁ is initial and has a loop on a,b to itself and a transition on a,b to y₂, and y₂ is a final state and has a loop on a,b to itself]. FA corresponding to r₁+r₂ can be determined as:

The resulting FA is a diagram with states z₁, z₂, z₃, and z₄.

Example Let r₁ = ((a+b)(a+b)) and the corresponding FA₁ be: [FA₁ diagram with two states, x₁ and x₂, where x₁ is initial and final and has transitions on a,b to x₂, and x₂ has transitions on a,b to x₁]. Also r₂ = (a+b)((a+b)(a+b)) or ((a+b)(a+b))(a+b) and FA₂ be: [FA₂ diagram with two states, y₁ and y₂, where y₁ is initial and has a loop on a,b to itself and a transition on a,b to y₂, and y₂ is a final state and has a loop on a,b to itself]. FA corresponding to r₁+r₂ can be determined as:

Hence the required FA will be as follows: [FA diagram with two states, z₁ and z₂, both with transitions on a,b to each other. z₁ is initial and final, z₂ is final].

Method2 (Concatenation of two FAs)

Using the FAs corresponding to r₁ and r₂, an FA can be built, corresponding to r₁r₂. This method can be developed considering the following examples.

💡 Why this matters: For concatenation, the FA must transition from the language of the first expression to the language of the second. This is achieved by, upon entering a final state of the first FA, also considering the start state of the second FA as a possible next state.

Example Let *r₁ = (a+b)b defines L₁ and FA₁ be: [FA₁ with two states: x₁ (initial), x₂ (final). x₁ has a transition on a to itself and on b to x₂. x₂ has a transition on a to x₁]. And *r₂ = (a+b)aa(a+b) defines L₂ and FA₂ be: [FA₂ with three states: y₁ (initial), y₂, y₃ (final). y₁ has transitions on a to y₂ and on b to y₁. y₂ has transitions on a to y₃ and on b to y₁. y₃ has a loop on a,b to itself].

Let FA₃ be an FA corresponding to r₁r₂, then the initial state of FA₃ must correspond to the initial state of FA₁ and the final state of FA₃ must correspond to the final state of FA₂. Since the language corresponding to r₁r₂ is the concatenation of corresponding languages L₁ and L₂, consists of the strings obtained, concatenating the strings of L₁ to those of L₂, therefore the moment a final state of first FA is entered, the possibility of the initial state of second FA will be included as well.

Since, in general, FA₃ will be different from both FA₁ and FA₂, so the labels of the states of FA₃ may be supposed to be z₁, z₂, z₃, ..., where z₁ stands for the initial state. Since z₁ corresponds to the states x₁, so there will be two transitions separately for each letter read at z₁. It will give two possibilities of states which correspond to either z₁ or different from z₁. This process may be expressed in the following transition table for all possible states of FA₃.

Hence the required FA will be as follows: [FA diagram with states z₁, z₂, z₃, z₄, z₅, z₆ and their transitions for a and b as defined in the table].

Note: Another example is discussed in the next lecture.

⭐ Key Takeaways

The most critical point is understanding that Kleene’s theorem Part III provides constructive methods to build FAs for any regular expression. For union, you build a new FA by pairing states from the two original FAs; a state is final if at least one of its component states is final. For concatenation, you must allow the FA to transition from the first sub-language to the second; this is done by, whenever you enter a final state of the first FA, adding the start state of the second FA as a possible next state. The construction process is systematic, using a transition table, and can result in a minimized number of states by only including reachable state combinations. The final states of the concatenated FA are those that contain a final state of the second FA.

🧠 Quick Revision Questions

1. When building an FA for the union of two regular expressions using Method 1, what does each new state represent?
2. In a union FA, when is a state considered a final (accepting) state?
3. What is the key idea in Method 2 for constructing an FA for the concatenation of two regular expressions?
4. In the concatenation method, why might a state contain multiple states from the second FA (e.g., z₅ = (x₂, y₁, y₃))?
5. Describe the state of the first FA that corresponds to the initial state of the concatenated FA, and describe the states of the second FA that correspond to the final states of the concatenated FA.

📘 Lecture 14 — Theory of Automata (CS402)

📖 Overview: This lecture continues the study of Kleene’s theorem Part III, which demonstrates how to construct Finite Automata (FAs) from Regular Expressions (REs). It covers three methods: building FA from REs using the union of FAs (Method 1), concatenation of FAs (Method 2), and closure of an FA (Method 3). Understanding these constructions is essential for proving the equivalence of regular expressions and finite automata.

🗂️ Topics Covered

Examples of Kleene’s theorem part III (method 1) continued, Kleene’s theorem part III (method 2: Concatenation of FAs), Examples of Kleene’s theorem part III (method 2: concatenation FAs) continued, Kleene’s theorem part III (method 3: closure of an FA), examples of Kleene’s theorem part III (method 3: Closure of an FA) continued.

📝 Lecture Summary

Examples of Kleene’s theorem part III (method 1) continued

The example demonstrates constructing an FA for the concatenation of two regular expressions. Let r₁ = ((a+b)(a+b))* and the corresponding FA₁ be given. Also, r₂ = (a+b)((a+b)(a+b))* or ((a+b)(a+b))*(a+b) and FA₂ be given. The FA corresponding to r₁r₂ is determined by taking the concatenation of FA₁ and FA₂.

The resulting FA is built by connecting the final state of FA₁ to the initial state of FA₂ using an ε-transition (or null transition). This ensures that strings from the language of r₁ are followed by strings from the language of r₂.

Method 2: (Concatenation of FAs)

Building an FA corresponding to the concatenation of two regular expressions, r₁r₂, uses the FAs corresponding to r₁ and r₂.

🔑 Definition — Kleene Part III Method 2: To construct an FA for r₁r₂, take FA₁ (for r₁) and FA₂ (for r₂), connect every final state of FA₁ to the initial state of FA₂ via an ε-transition, and make the initial state of FA₁ the new initial state and all final states of FA₂ the new final states.

📐 Formula: FA(r₁r₂) = ε-connection from FA₁ final states → FA₂ initial state

📌 Example: For r₁ = ((a+b)(a+b))* and r₂ = (a+b)((a+b)(a+b))*, we construct the new FA as shown in the lecture diagram. The old states are paired with new states after reading a and b:

• Old States z₁- ≡ (x₁, y₁): on a → (x₂, y₂) ≡ z₂; on b → (x₂, y₂) ≡ z₂
• Old States z₂+ ≡ (x₂, y₂): on a → (x₁, y₁) ≡ z₁; on b → (x₁, y₁) ≡ z₁

This yields a two-state FA that accepts the concatenated language.

Method 3: (Closure of an FA)

Building an FA corresponding to r*, using the FA corresponding to r. If the given FA already accepts the language expressed by the closure of a certain RE, then the given FA is the required FA. Otherwise, the method is developed considering examples.

🔑 Definition — Closure of an FA: Closure of an FA is the same as concatenation of an FA with itself, except that the initial state of the required FA is a final state as well. The initial state of the given FA corresponds to both the initial state of required FA and a non-final state of the required FA.

💡 Why this matters: The closure operation (Kleene star) allows an FA to accept zero or more repetitions of strings from the original language, making it a fundamental operation in regular language theory.

📌 Example 1: Let r = (a+b)b and the corresponding FA be given. Then the FA corresponding to r is determined using the state transition table:

• Old States z₁± ≡ x₁: on a → x₁ ≡ z₂; on b → (x₂, x₁) ≡ z₃
• Non-final z₂ ≡ x₁: on a → x₁ ≡ z₂; on b → (x₂, x₁) ≡ z₃
• z₃+ ≡ (x₂, x₁): on a → x₁ ≡ z₂; on b → (x₂, x₁) ≡ z₃

The resulting FA has z₁ as a final state (since initial state is also final for closure).

📌 Example 2: Let r = (a+b)aa(a+b) and the corresponding FA be given. Then the FA corresponding to r* is determined:

• Final z₁± ≡ y₁: on a → y₂ ≡ z₃; on b → y₁ ≡ z₂
• Non-final z₂ ≡ y₁: on a → y₂ ≡ z₃; on b → y₁ ≡ z₂
• z₃ ≡ y₂: on a → (y₃, y₁) ≡ z₄; on b → y₁ ≡ z₂
• z₄+ ≡ (y₃, y₁): on a → (y₃, y₁, y₂) ≡ z₅; on b → (y₃, y₁) ≡ z₄
• z₅+ ≡ (y₃, y₁, y₂): on a → (y₃, y₁, y₂) ≡ z₅; on b → (y₃, y₁) ≡ z₄

📌 Example 3: Consider an FA accepting the language of strings with 'b' as second letter. The FA has states y₁-, y₂, y₃+, y₄. Then the FA corresponding to r* is determined:

• z₁± ≡ y₁: on a → y₂ ≡ z₂; on b → y₂ ≡ z₂
• z₂ ≡ y₂: on a → y₄ ≡ z₃; on b → (y₃, y₁) ≡ z₄
• z₃ ≡ y₄: on a → y₄ ≡ z₃; on b → y₄ ≡ z₃
• z₄+ ≡ (y₃, y₁): on a → (y₃, y₁, y₂) ≡ z₅; on b → (y₃, y₁, y₂) ≡ z₅
• z₅+ ≡ (y₃, y₁, y₂): on a → (y₃, y₁, y₂, y₄) ≡ z₆; on b → (y₃, y₁, y₂) ≡ z₅
• z₆ ≡ (y₁, y₁, y₂, y₄): on a → (y₁, y₁, y₂, y₄) ≡ z₆; on b → (y₁, y₁, y₂, y₄) ≡ z₆

⭐ Key Takeaways

The most critical concepts from this lecture are: (1) Kleene's theorem Part III provides systematic methods to construct FAs from any regular expression using operations of union, concatenation, and closure on FAs. (2) For concatenation (Method 2), we connect each final state of the first FA to the initial state of the second FA via an ε-transition, making the initial state of the first FA the new start and all final states of the second FA the final states. (3) For closure (Method 3), we treat it as concatenation of the FA with itself, but crucially, the initial state of the resulting FA must also be a final state to allow zero repetitions. (4) The construction process uses state transition tables that combine old states (possibly pairs or sets of original states) with new state names. (5) These constructions are foundational for proving the equivalence of regular expressions and finite automata, and are essential for converting REs into practical automata implementations.

🧠 Quick Revision Questions

1. In Method 2 (concatenation of FAs), what is the role of ε-transitions and how are the initial and final states of the resulting FA determined?

2. How does the closure operation (Method 3) differ from concatenation, and why must the initial state be a final state in the closure FA?

3. For the FA accepting strings with 'b' as second letter (Example 3), trace the transition of string "aab" through the closure FA, showing each state visited.

4. Given an FA for r = (a+b)b, construct the transition table for the closure FA r and write the final state(s) that accept the empty string.

5. Explain why the number of states often increases when constructing the closure FA compared to the original FA, using the examples from the lecture.

📘 Lecture 15 — Examples of Kleene’s theorem part III (method 3), NFA, examples, avoiding loop using NFA, example, converting FA to NFA, examples, applying an NFA on an example of maze

📖 Overview: This lecture continues the discussion of Kleene’s theorem Part III (method 3) and introduces the Nondeterministic Finite Automaton (NFA) as an intermediate structure between FA and TG. It demonstrates how NFAs can eliminate loops from FAs, how to convert an FA to an equivalent NFA, and presents a practical application of NFA in artificial intelligence using a maze example.

🗂️ Topics Covered

The lecture covers observations about initial states in Kleene’s theorem, the formal definition of NFA with observations, examples of NFAs accepting specific languages, the technique of eliminating loops at states by converting FA to NFA, examples of converting FA to equivalent NFA, and an application of NFA in solving a maze problem in artificial intelligence.

📝 Lecture Summary

Note (Observation about Initial State in Kleene’s Theorem)

It is to be noted that as observed in the examples discussed in previous lecture, if at the initial state of the given FA, there is either a loop or an incoming transition edge, the initial state corresponds to the final state and a non-final state as well, of the required FA. Otherwise, the initial state of given FA will only correspond to a single state of the required FA (i.e. the initial state which is final as well).

Nondeterministic Finite Automaton (NFA) — Definition

An NFA is a TG with a unique start state and a property of having single letter as label of transitions. An NFA is a collection of three things:

1. Finite many states with one initial and some final states
2. Finite set of input letters, say, Σ = {a, b, c}
3. Finite set of transitions, showing where to move if a letter is input at certain state (Λ is not a valid transition), there may be more than one transition for certain letters and there may not be any transition for certain letters.

Observations

It may be observed, from the definition of NFA, that the string is supposed to be accepted, if there exists at least one successful path, otherwise rejected. It is to be noted that an NFA can be considered to be an intermediate structure between FA and TG.

Example (NFA accepting a and ab)

An NFA is presented (in the lecture) that accepts the language consisting of a and ab.

Example (NFA accepting strings containing aa)

An NFA is presented that accepts the language of strings, defined over Σ = {a, b}, containing aa.

Note (Eliminating Loops Using NFA)

It is to be noted that NFA helps to eliminate a loop at certain state of an FA. This process is done by converting the loop into a circuit. But during this process the FA remains no longer FA and is converted to a corresponding NFA.

Example (Eliminating a Loop at State 7)

Consider a part of an FA with alphabet Σ = {a,b,c,d} that has a loop at state 7. To eliminate the loop at state 7, the corresponding NFA may be constructed, where the loop is replaced by a circuit structure, introducing nondeterminism.

Converting an FA to an equivalent NFA

It is to be noted that according to Kleene’s theorem, if a language can be accepted by an FA, then there exists a TG accepting that language. Since an NFA is a TG as well, therefore there exists an NFA accepting the language accepted by the given FA. In this case these FA and NFA are said to be equivalent to each other.

Example (Converting an FA for (a+b)*b to NFA)

Consider the following FA corresponding to *(a+b)b:

• (Diagram of FA with states, transitions for a and b, and a final state)

The above FA may be equivalent to the following NFA:

• (Diagram of NFA with nondeterministic transitions)

Question: Can the structure of above NFA be compared with the corresponding RE?

Example (Converting another FA to NFA)

Consider the following FA:

• (Diagram of another FA)

The above FA may be equivalent to the following NFA:

• (Diagram of corresponding NFA)

Question: Can the structure of above NFA be compared with the corresponding RE?

Application of an NFA — Maze Example

There is an important application of an NFA in artificial intelligence, which is discussed in the following example of a maze:

A maze is presented with labeled positions:

• 1, 2, 3 (top row)
• 4, L, 5, O (second row)
• 6, M, 7, P (third row)
• 8, N, 9 (bottom row)
• - at start position 1
• + at an exit/goal position

An NFA can model the possible paths through the maze, where each state represents a location and transitions represent allowable moves. The NFA accepts if there exists at least one successful path from the start (-) to the goal (+).

💡 Why this matters: This demonstrates how NFAs, with their nondeterministic nature, can efficiently model search problems and pathfinding in AI, where multiple possibilities must be explored simultaneously.

⭐ Key Takeaways

The critical points to remember are: (1) NFA is a TG with single-letter transitions and a unique start state, allowing multiple or zero transitions for a given letter; (2) a string is accepted by an NFA if there exists at least one successful path from start to final state; (3) NFAs serve as intermediate structures between FA and TG and are useful for eliminating loops from FAs; (4) every FA can be converted to an equivalent NFA by replacing loops with circuits, introducing nondeterminism; (5) NFAs have practical applications in artificial intelligence, such as modeling mazes and search problems where multiple paths must be explored.

🧠 Quick Revision Questions

1. What are the three components that define an NFA?
2. How does the acceptance condition of an NFA differ from that of a deterministic FA?
3. Why can NFA be considered an intermediate structure between FA and TG?
4. Explain the process of eliminating a loop at a state in an FA by converting it to an NFA.
5. In the maze application, why is an NFA particularly suitable for modeling pathfinding problems compared to a deterministic FA?

📘 Lecture 16 — Applying an NFA on an example of maze, NFA with null string, examples, RE corresponding to NFA with null string (task), converting NFA to FA (method 1,2,3) examples

📖 Overview: This lecture demonstrates the practical application of an NFA to solve a maze problem and formally introduces NFA with null string (NFA-Λ). It then details three distinct methods for converting any NFA into an equivalent finite automaton (FA) , providing step-by-step examples for each approach. Understanding these conversions is essential for simplifying automata and building deterministic models.

🗂️ Topics Covered

The lecture covers applying an NFA to model paths in a maze, defines NFA-Λ with examples, discusses the relationships between FA, NFA, NFA-Λ, and TG, and presents three methods for converting NFA to FA: using regular expressions (Method 1), building a transition diagram with an empty state (Method 2), and constructing a transition table with combined states (Method 3).

📝 Lecture Summary

Application of an NFA

An important application of NFA in artificial intelligence is demonstrated using a maze of labeled boxes (1-9, L, M, N, O, P, +, -). The initial state is - and the final state is +. Movement is allowed only between boxes not labeled L, M, N, O, P. An NFA using only the single letter a is constructed to model all possible paths. In this NFA, each acceptable move corresponds to reading an 'a'.

It is observed that the shortest path from initial to final state consists of six steps, meaning the shortest accepted string is aaaaaa. The next longer accepted string is aaaaaaaa (eight a's). If this NFA is treated as a TG, the corresponding regular expression is aaaaaa(aa)*, which shows there are infinitely many required ways (all strings of a's with an even number of a's after the first six).

🔑 Definition — NFA (Nondeterministic Finite Automaton): An automaton where, for a given state and input symbol, there may be zero, one, or multiple possible next states.

💡 Why this matters: This maze example shows how NFAs can model computational problems with multiple possible paths, a core idea in AI pathfinding and state-space search.

NFA with Null String

Definition: If in an NFA, Λ (null string) is allowed to be a label of an edge, then the NFA is called NFA with Λ (NFA-Λ).

An NFA-Λ is a collection of three things:

1. Finite many states with one initial and some final states.
2. Finite set of input letters, say Σ = {a, b, c}.
3. Finite set of transitions, showing where to move if a letter is input at certain state. There may be more than one transition for a certain letter and there may not be any transition for a certain letter. The transition of Λ is also allowed at any state.

📌 Example 1: An NFA-Λ is presented that accepts the language of strings, defined over Σ = {a, b}, ending in b.

📌 Example 2: An NFA-Λ is presented that accepts the language of strings, defined over Σ = {a, b}, ending in a.

Note: Every FA may be considered to be an NFA-Λ as well, but the converse may not be true. Similarly, every NFA-Λ may be considered to be a TG as well, but the converse may not be true.

🔑 Definition — NFA-Λ (NFA with Null String): An NFA where transitions labeled with the null string (Λ) are permitted, allowing state changes without consuming any input symbol.

NFA to FA — Method 1

Method 1: Since an NFA can be considered to be a TG as well, a regular expression (RE) corresponding to the given NFA can be determined (using Kleene’s theorem). Again using the methods discussed in the proof of Kleene’s theorem, an FA can be built corresponding to that RE. Hence, for a given NFA, an FA can be built equivalent to the NFA. Examples have, indirectly, been discussed earlier.

NFA to FA — Method 2

Method 2: Since in an NFA, there may be more than one transition for a certain letter and there may not be any transition for a certain letter, starting from the initial state corresponding to the initial state of the given NFA, the transition diagram of the corresponding FA can be built by:

• Introducing an empty state (Ø) for a letter having no transition at a certain state.
• Introducing a state corresponding to the combination of states (e.g., {1,2}) for a letter having more than one transitions.

📌 Example 1: Consider a given NFA. Using Method 2, the above NFA is converted to an equivalent FA. The FA includes an empty state to handle missing transitions.

📌 Example 2: A simple NFA that accepts the language of strings defined over Σ = {a,b}, consisting of bb and bbb. The NFA is converted to the following FA, which includes an empty state to handle transitions for 'a' and 'b' that are not defined in the NFA.

NFA to FA — Method 3

Method 3: As discussed earlier, in an NFA, there may be more than one transition for a certain letter and there may not be any transition for certain letter. Starting from the initial state corresponding to the initial state of the given NFA, the transition table along with new labels of states of the corresponding FA can be built by:

• Introducing an empty state for a letter having no transition at a certain state.
• Introducing a state corresponding to the combination of states for a letter having more than one transitions.

Further examples of this method are discussed in the next lecture.

⭐ Key Takeaways

The key takeaway is that NFAs are not just theoretical constructs but have practical applications, such as modeling pathfinding problems in AI using a regular expression like aaaaaa(aa)*. The lecture formally defines an NFA-Λ, which adds null transitions, and places it in the hierarchy: FA ⊆ NFA ⊆ NFA-Λ ⊆ TG. Most critically, three distinct methods for converting any NFA (with or without null) into an equivalent FA are presented: Method 1 converts to a TG then to an RE to build an FA; Method 2 builds a transition diagram directly using a new empty state for missing transitions and combined states for multiple transitions; Method 3 builds a transition table similarly, creating new state labels from combinations. These methods are essential for obtaining deterministic models from nondeterministic specifications.

🧠 Quick Revision Questions

1. What regular expression describes the language of paths in the maze example, and what does it imply about the number of possible paths?
2. What is the formal definition of an NFA with null string (NFA-Λ), and how does it differ from a standard NFA?
3. What is the process for converting an NFA to an FA using Method 1?
4. Describe the two key strategies used in Method 2 to handle missing transitions and multiple transitions in an NFA when building the equivalent FA.
5. What is the fundamental difference between Method 2 and Method 3 for converting an NFA to an FA?

📘 Lecture 17 — Converting NFA to FA (Method 3), NFA and Kleene’s Theorem

📖 Overview: This lecture covers Method 3 for converting an NFA to an FA by introducing an empty state and combination states. It then explores how NFAs help prove Kleene’s Theorem Part III, demonstrating two methods for constructing FAs corresponding to regular expressions through decomposition, union, concatenation, and closure.

🗂️ Topics Covered

Method 3 for NFA-to-FA conversion with a worked example, transition table construction, and transition diagram; NFA and Kleene’s theorem (Part III) with two methods: Method 1 builds FAs for simple languages {a}, {b}, {Λ}, then Method 2 constructs NFAs for union, concatenation, and closure of FAs—illustrated by an NFA corresponding to the union of two FAs.

📝 Lecture Summary

Method 3: Converting NFA to FA

In an NFA, there may be more than one transition for a certain letter or none at all. To convert it to an FA, starting from the initial state of the NFA, build a transition table with new state labels by introducing an empty state (for letters with no transition) and a combination state (for letters with multiple transitions).

Example: Consider the following NFA that accepts the language of strings containing bb.

The transition table for the corresponding FA is constructed as:

The corresponding transition diagram follows as:

• z₁⁻ — on 'a' goes to z₁, on 'b' goes to z₂
• z₂ — on 'a' goes to z₁, on 'b' goes to z₃⁺
• z₃⁺ — on 'a' goes to z₄⁺, on 'b' goes to z₃⁺
• z₄⁺ — on 'a' goes to z₄⁺, on 'b' goes to z₃⁺

🔑 Definition — Empty State (∅): A state introduced when a letter has no transition from a given NFA state; it behaves as a sink state in the FA. 📐 Method 3 Rule: For each letter, the new state is the set of all NFA states reachable (including ∅ if none) → represents deterministic behavior.

NFA and Kleene’s Theorem

Kleene’s Theorem Part III states that there exists an FA corresponding to any given regular expression (RE). For simple REs like r = aa+bbb or r = a(a+b)*, FAs can be constructed directly. For complicated REs, the RE is decomposed into simple REs, and FAs for sum, concatenation, and closure are combined. NFAs also help in proving this theorem.

💡 Why this matters: NFAs provide a systematic way to construct FAs for complex regular expressions by breaking them into smaller, manageable parts.

NFA and Kleene’s Theorem — Method 1

Build NFAs for simple languages, then convert them to equivalent FAs.

Example: Construct FAs for languages L₁ = {a}, L₂ = {b}, and L₃ = {Λ}.

Step 1: Build NFA₁, NFA₂, and NFA₃:

• NFA₁: Start state → on 'a' → final state (accepts {a})
• NFA₂: Start state → on 'b' → final state (accepts {b})
• NFA₃: Start and final state are the same (accepts {Λ})

Step 2: Since every NFA has an equivalent FA, convert the NFAs to FAs:

• FA₁: Accepts {a} (single transition on 'a' from start to final)
• FA₃: Accepts {Λ} (start state is final)

NFA and Kleene’s Theorem — Method 2

If an NFA can be built corresponding to union, concatenation, and closure of FAs for REs, converting that NFA to an FA yields the FA for the given RE.

NFA Corresponding to Union of FAs

Method: Introduce a new start state and connect it with the states originally connected with the old start state using the same transitions. Then remove the -ve sign (non-final status) from the old start state. This creates non-determinism, resulting in an NFA.

Example: Consider FA₁ (accepts language with 'b') and FA₂ (accepts language with 'a').

FA₁: States with transitions on 'a' and 'b' FA₂: States with transitions on 'a' and 'b'

To construct the NFA equivalent to FA₁ ∪ FA₂:

1. Introduce a new start state (-)
2. From the new start state, add transitions: on 'a' to the states reachable from the old start of FA₁ on 'a' and from the old start of FA₂ on 'a'; on 'b' similarly.
3. Remove the -ve sign from the old start states.
4. This creates multiple transitions from the new start state, introducing non-determinism.

The resulting NFA accepts strings that are in either FA₁ or FA₂.

⭐ Key Takeaways

1. Method 3 for NFA-to-FA conversion uses combination states (sets of NFA states) and an empty state (∅) to handle multiple or missing transitions, ensuring deterministic behavior.
2. Kleene’s Theorem Part III can be proven by decomposing complex REs into simple components and using NFAs for union, concatenation, and closure operations.
3. Method 1 builds NFAs for atomic languages {a}, {b}, {Λ}, then converts them to equivalent FAs.
4. Method 2 constructs NFAs for union by introducing a new start state with transitions to states connected to old start states, creating non-determinism.
5. The transition table method systematically tracks all possible NFA state combinations as single FA states, ensuring the final FA is deterministic.

🧠 Quick Revision Questions

1. In Method 3 for NFA-to-FA conversion, what does the empty state (∅) represent, and when is it introduced?
2. How does the transition table in the example handle the case where reading 'a' from state x₂ leads to no transition?
3. In Method 1 of Kleene’s theorem, what are the three atomic languages for which NFAs are first built?
4. When constructing an NFA for the union of two FAs, what is the purpose of introducing a new start state?
5. Why is the NFA in Method 2 considered non-deterministic after adding the new start state?

📘 Lecture 18 — Theory of Automata

📖 Overview: This lecture covers the construction of NFAs corresponding to the union, concatenation, and closure (Kleene star) of finite automata. It provides systematic methods and detailed examples for building complex automata from simpler ones, which is fundamental for understanding regular operations and expressions.

🗂️ Topics Covered

NFA corresponding to union of FAs with an example, NFA corresponding to concatenation of FAs with methodology and three detailed examples (no FA accepts Null string, FA₂ accepts Null string, both FAs accept Null string), and NFA corresponding to closure of an FA with methodology and two examples.

📝 Lecture Summary

Example (Union of FAs)

The lecture begins by presenting two FAs, FA₁ and FA₂, and showing the construction of an NFA equivalent to FA₁ ∪ FA₂. FA₁ has states p- (initial) and q, with transitions on a and b between them. FA₂ has states 1-, 2, 3, 4, 5, and 6+, with a more complex transition structure. The resulting NFA merges both automata by connecting the initial states to a new start state with ε-transitions.

🔑 Definition — Union of FAs: A construction that yields an automaton accepting strings that are accepted by either FA₁ or FA₂.

NFA corresponding to Concatenation of FAs

Method: Introduce additional transitions for each letter connecting each final state of the first FA with the states of second FA that are connected with the initial state of second FA corresponding to each letter of the alphabet. Remove the +ve sign of each final state of first FA and –ve sign of the initial state of second FA. This creates non-determinism at final states of first FA, yielding the required NFA.

Note: If first FA accepts the Null string, then every string accepted by second FA must be accepted by the concatenation. If second FA accepts Null string, then every string accepted by first FA must be accepted — in this case, the +ve sign of final states of first FA will not be removed. If both FAs accept the Null string, then the Null string must be accepted by the required FA.

Example (No FA accepts Null string)

FA₁ has states 1– (initial), 2, 3, 4, and 5+ with transitions on a and b. FA₂ has states p- (initial), q, and r+ with transitions on a and b. The resulting NFA equivalent to FA₁FA₂ is constructed by:

• Removing the + sign from state 5 and the – sign from state p
• Adding transitions from state 5 (former final of FA₁) to states reachable from p in FA₂

📌 Example: FA₁ accepts strings ending in 'a' (state pattern), FA₂ accepts strings containing 'b'. Their concatenation accepts strings where a string ending in 'a' is followed by a string containing 'b'.

Example (FA₂ accepts Null string)

FA₁ has states p- (initial) and q with transitions on a and b. FA₂ has states with final state r+ that accepts all strings (a,b at r). Since FA₂ accepts the Null string, the +ve sign of final states of FA₁ is not removed. The resulting NFA equivalent to FA₁FA₂ preserves the final status of FA₁'s accepting states.

Example (Both FAs accept Null string)

FA₁ has states 1± (initial and final) with transitions on a,b to 2 and 3, with 3 being final. FA₂ has states with initial state and final state. Both accept the Null string. The resulting NFA equivalent to FA₁FA₂ shows the construction where final sign of first FA's states remains, and transitions connect states appropriately.

NFA corresponding to the Closure of an FA

Method: Introduce an initial state which should be final as well (so that the Null string is accepted). Connect it with the states originally connected with the old start state with the same transitions as the old start state. Remove the –ve sign of old start state. Introduce new transitions, for each letter, at each of the final states (including new final state) with those connected with the old start state. This creates non-determinism and results in the required NFA.

Example (Closure)

Consider an FA with a single initial state. The FA* accepts only the additional string which is the Null string. Simply making the initial state final would allow unwanted strings to be accepted. The required NFA introduces a new initial state with appropriate transitions.

Example (Another Closure)

Consider an FA with states and transitions on a and b. The FA* accepts only the additional Null string. As observed, the required NFA is constructed by introducing the new initial state shown in the diagram.

💡 Why this matters: The closure construction is essential because simply making the initial state final would incorrectly accept strings that the original FA would reject.

⭐ Key Takeaways

The most critical concepts from this lecture are: (1) For union, NFAs combine FAs using a new start state with ε-transitions to the original initial states. (2) For concatenation, transitions from final states of the first FA are added to states reachable from the initial state of the second FA, with careful handling of the + and – signs based on whether each FA accepts the Null string. (3) For closure (Kleene star), a new initial state that is also final must be introduced, with transitions mimicking the old start state and additional transitions from all final states. (4) The Null string acceptance rules are critical: if the second FA accepts ε, final signs of the first FA are preserved; if both accept ε, the concatenation also accepts ε. (5) The closure construction prevents acceptance of unwanted strings that would occur if the original initial state were simply made final.

🧠 Quick Revision Questions

1. When constructing the NFA for concatenation of two FAs, under what conditions do you not remove the + sign from the final states of the first FA?
2. What additional transitions are introduced in the closure (Kleene star) construction for an FA, and why must a new initial state be introduced?
3. In the union construction, how do you connect the two separate FAs to form the NFA equivalent to FA₁ ∪ FA₂?
4. If FA₁ accepts the Null string but FA₂ does not, what modification is needed in the concatenation construction?
5. Why can't you simply make the initial state of an FA final to construct its closure (FA*)?

📘 Lecture 19 — NFA corresponding to Closure of FA, Examples, Memory required to recognize a language, Example, Distinguishing one string from another, Example, Theorem, Proof

📖 Overview: This lecture explores how to construct NFAs corresponding to the closure (Kleene star) of an FA, and examines the memory requirements for recognizing different languages. It introduces the crucial concept of distinguishable strings, which forms the basis for a fundamental theorem about the minimum number of states required in any FA that recognizes a given language.

🗂️ Topics Covered

The lecture covers NFA construction for the closure of FA with examples, memory requirements to recognize languages including detailed analysis for L₃ and L₂₀ languages, the concepts of distinguishable and indistinguishable strings with examples, and the theorem stating that if n strings are pairwise distinguishable with respect to a language L, then any FA recognizing L must have at least n states, along with its complete proof.

📝 Lecture Summary

Example (Closure of FA)

Consider the following FA that accepts all strings. It can be observed that FA* not only accepts the Null string but every other string as well. Here we don’t need separate initial and final state. Hence an NFA corresponding to FA* may be constructed as shown.

📌 Example: For the given FA with states 1± and 2+ (both initial and final), the NFA for the closure keeps the same structure but allows transitions without needing distinct initial/final state separation.

Memory required to recognize a language

Memory required to recognize a language means to look at the machine which can recognize a language. An FA can be considered to be a simple model of computation, and every regular language is associated with a certain FA. To recognize a language, there is a restriction that there is a single pass from left to right for any string to decide whether it belongs to a certain language. This helps to remember information about the initial part of the string read so far.

Consider L = {w ∈ {a,b}* : w neither ends in ab nor in ba}. i.e. L is the language of strings, defined over Σ = {a,b}, consisting of Λ, a, b and strings ending in aa or bb. As seen in the above FA, seven states are required to recognize the language L, while on the other hand it is very hard to recognize the language PALINDROME.

Now consider another language L₃ of strings of length three or more, defined over Σ = {a,b}, and the third letter from the right is a. As discussed by Martin, there is a straightforward method to build an FA recognizing L₃: a distinct state for every possible substring of length less than or equal to 3. It is obvious that for each length i, i=0,1,2,3, of substring, the number of states are 2ⁱ and thus total number of states required to recognize the language L₃ are 2⁰+2¹+2²+2³ = 2³⁺¹-1 = 15 (using 2⁰+2¹+2²+...+2ⁿ = 2ⁿ⁺¹-1).

📐 Formula: Total states = 2ⁿ⁺¹ - 1, where n is the position from the right being checked.

Remark: Let L₂₀ be the language of strings of length 20 or more, defined over Σ = {a,b}, and the 20th letter from the right is 1, then following the previous method, number of states for the corresponding FA is 2²⁰⁺¹-1 = 2,097,151. However, it may be noted that any portion of memory of a computer that can accommodate 21 bits can be in 2²¹ possible states i.e. 2²¹ possible choices for the informational content.

💡 Why this matters: This shows the exponential growth in states required for languages defined by a fixed position from the right, and how this relates to computer memory requirements.

Distinguishable strings and Indistinguishable strings

Two strings x and y, belonging to Σ*, are said to be distinguishable w.r.t a language L ⊆ Σ* if there exists a string z belonging to Σ* such that xz ∈ L but yz ∉ L or xz ∉ L but yz ∈ L.

Two strings x and y, belonging to Σ*, are said to be indistinguishable with respect to a language L ⊆ Σ* if for every string z belonging to Σ*, either both xz and yz ∈ L or both don’t belong to L.

🔑 Definition — Distinguishable strings: Strings x and y are distinguishable w.r.t. L if there is some suffix z that causes one concatenation to be in L and the other not.

📌 Example: Let L be the language of strings, defined over Σ = {0,1}, ending in 01. The strings 110 and 010011 are distinguishable w.r.t L, as there exists 1 belonging to Σ* such that 1101 belongs to L but 0100111 doesn’t belong to L. But 111 and 010011 are indistinguishable, for 1 belonging to Σ* such that both 1111 and 010011 don’t belong to L i.e. for every z belonging to Σ*, either both 111z and 01001z belong to L, or both don’t belong to L.

Theorem

Statement: If L is a language over an alphabet Σ and for integer n there are n strings from Σ, any two of which are distinguishable* w.r.t. language L, then any FA that recognizes L must have at least n states. (Note: There may not exist any FA which recognizes the given language.)

🔑 Definition — Theorem implication: This provides a lower bound on the number of states needed for any FA recognizing L.

📐 Proof: Let S be set of strings, any two of which are distinguishable w.r.t. language L. Let F₁ be the FA which recognizes the language L. To prove the theorem, it is sufficient to show that any two strings under F₁ must end in different states i.e. corresponding to each string x belonging to S, F₁ ends in distinct states. Thus if S has n strings then it is to be shown that F₁ has at least n states.

Let x and y be any two strings from S. By supposition any two strings of S are distinguishable w.r.t. L, so there exists a string z belonging to Σ* such that only one of xz and yz belongs to L i.e. F₁ ends in a final state either for xz or yz which shows that F₁ ends in distinct states for xz and yz.

Let F₁ be ended in same state for both the strings x and y, which shows that F₁ ends in same state for both xz and yz, a contradiction as x and y being distinguishable implies xz and yz are ended at distinct states of F₁. Hence F₁ does not end in a same state for both strings x and y, which shows that each pair of strings belonging to S ends in different states. Hence F₁ must contain at least n states.

💡 Why this matters: This theorem provides the theoretical foundation for proving that certain languages cannot be recognized by FAs with fewer than a specific number of states, and is essential for understanding the Myhill-Nerode theorem.

⭐ Key Takeaways

The most critical concepts to remember are: 1) The number of states required for an FA recognizing a language defined by a specific position from the right (like the nth letter) is 2ⁿ⁺¹ - 1, which grows exponentially; 2) Two strings are distinguishable with respect to a language L if there exists some suffix that separates them (one concatenation is in L, the other is not); 3) If n strings are pairwise distinguishable w.r.t. L, then any FA recognizing L requires at least n states — this is proven by contradiction, showing each distinguishable pair must end in different states; 4) Indistinguishable strings always behave the same way when any suffix is appended; 5) This theorem provides a lower bound on FA size and can prove that certain languages are not regular if infinite distinguishable strings exist.

🧠 Quick Revision Questions

1. How many states are required for an FA recognizing the language where the 5th letter from the right is 'a' over alphabet {a,b}?

2. Why can't two distinguishable strings end in the same state in an FA that recognizes language L?

3. In the language L ending in "01", are the strings "101" and "010" distinguishable or indistinguishable? Justify your answer.

4. What is the relationship between the number of states in an FA and the number of pairwise distinguishable strings with respect to the language it recognizes?

5. If we have 100 pairwise distinguishable strings for language L, what can we conclude about any FA that recognizes L?

📘 Lecture N0. 20 — Theory of Automata

📖 Overview: This lecture begins by applying a previous theorem to show the minimum number of states required for an FA accepting a language defined by the 20th letter from the right. It then introduces the concept of finite automata with output, specifically defining and demonstrating the Moore machine, a model that produces an output character for each state entered.

🗂️ Topics Covered

The lecture covers an example demonstrating that any FA accepting the language L20 (strings where the 20th letter from the right is 1) must have at least 2^20 states, followed by a note on the memory required. The main topic shifts to finite automata with output, introducing the Moore machine, its formal definition, and providing a complete example with a transition table, transition diagram, input string, and output string.

📝 Lecture Summary

Example

The lecture examines the language L₂₀ = {w ∈ {0,1}* : |w| ≥ 20 and the 20th letter of w, from right is, 1}. Let S be the set of all strings of length 20, any two of which are distinguishable with respect to L₂₀. There are 2²⁰ strings in S. Let x and y be any two distinct strings in S, differing in the i-th letter from the left.

If i=1, they differ by the first letter from left. By definition of L₂₀, one string is in L₂₀ while the other is not, as shown below: 0... . 1... .

For z = Λ (empty string), one of xz and yz belongs to L₂₀, so x and y are distinguishable.

If i=2, they differ by the 2nd letter from left. For any z ∈ Σ* with |z|=1, either xz or yz belongs to L₂₀, because the 20th letter from the right of xz and yz is the 2nd letter from left of x and y, as shown below: . 0 ... . z . 1 ... . z

Continuing this process, any pair of strings x and y in S will be distinguishable with respect to L₂₀. Since S contains 2²⁰ strings, all pairwise distinguishable, using the theorem, any FA accepting L₂₀ must have at least 2²⁰ states. 💡 Why this matters: This demonstrates a powerful lower bound on the number of states required for a language defined by a distant character, showing exponential state requirements for simple-looking conditions.

Note

Using Martin’s method, there exists an FA having 2²⁰⁺¹ - 1 = 2,097,151 states. This indicates the memory required to recognize L₂₀ is the memory of a computer that can accommodate 21-bits, i.e., the computer can be in 2²¹ possible states.

Finite Automaton with output

So far, finite automata are associated only with regular expressions or languages. A key question is whether an FA can generate an output string corresponding to each input string. The answer is yes. Such machines are called machines with output. There are two types: Moore machine and Mealy machine.

Moore machine

A Moore machine consists of the following:

• A finite set of states q₀, q₁, q₂, ... where q₀ is the initial state.
• An alphabet of letters Σ = {a,b,c,...} from which input strings are formed.
• An alphabet Γ = {x,y,z,...} of output characters from which output strings are generated.
• A transition table that shows for each state and each input letter what state is entered next.
• An output table that shows what character is printed by each state as it is entered.

🔑 Definition — Moore machine: A finite automaton that produces an output character for each state it enters, including the initial state before reading any input.

Note: In a Moore machine, no state is designated to be a final state, so there is no question of accepting any language. However, the relation between an input string and the corresponding output string may be identified. The initial state is not especially important, as restarting the machine from the state it was left off is possible.

Example

Consider a Moore machine with states q₀, q₁, q₂, q₃ where q₀ is the start state, Σ = {a,b}, and Γ = {0,1}.

The transition table is:

The transition diagram corresponding to the previous transition table may be:

[Diagram with states labeled: q₀ (1), q₁ (0), q₂ (0), q₃ (1). Transitions: q₀ --a--> q₁, q₀ --b--> q₃; q₁ --a--> q₃, q₁ --b--> q₁; q₂ --a--> q₀, q₂ --b--> q₃; q₃ --a--> q₃, q₃ --b--> q₂]

It is to be noted that the states are labeled along with the characters to be printed. Running the string abbabbba over the above machine, the corresponding output string will be 100010101, which can be determined by the following table as well:

It may be noted that the length of output string is 1 more than that of input string, as the initial state prints out the extra character 1 before the input string is read. 📌 Example: Given the Moore machine above and the input string "a", the sequence of states is q₀ → q₁. The output is the character printed by q₀ (which is '1') followed by the character printed by q₁ (which is '0'), resulting in the output string "10". For an input string "ab", the states are q₀ → q₁ → q₁. The outputs are: q₀ prints 1, q₁ prints 0, and then q₁ prints 0, giving output "100".

⭐ Key Takeaways

The key takeaway is that the number of states required for an FA can grow exponentially with simple language constraints, as shown by the 2²⁰ state lower bound for L₂₀. A Moore machine is a fundamental type of finite automaton with output that produces an output character every time a state is entered, including the initial state. Unlike standard FAs, Moore machines do not accept languages, but rather define a mapping from input strings to output strings. The length of the output string from a Moore machine is always one greater than the length of the input string. When reading an input string, the next state is determined by the current state and the input letter, and the output of that next state is printed.

🧠 Quick Revision Questions

1. Why must any FA accepting L₂₀ have at least 2²⁰ states?
2. What is the key difference between a finite automaton that accepts a language and a Moore machine?
3. What are the four essential components that define a Moore machine?
4. For the Moore machine in the example, what is the output string for the input string "ba"?
5. Why is the output string from a Moore machine always one character longer than the input string?

📘 Lecture 21 — Theory of Automata

📖 Overview: This lecture introduces the Mealy machine, compares it with the Moore machine, and demonstrates how to construct specific Mealy machines such as the complementing machine and the incrementing machine. Understanding these machines is crucial for grasping how finite automata can generate output sequences based on input strings.

🗂️ Topics Covered

Example of Moore machine showing relation between input substrings and output characters; definition and working of Mealy machine with examples; complementing machine that produces 1's complement of input; construction of the incrementing machine that adds 1 to a binary number read from right to left, including overflow situation.

📝 Lecture Summary

Example

To identify the relation between the input strings and the corresponding output strings in the given Moore machine, if the string bbbabaabbaa is run, the output string will be 000010000010.

It can be observed from the Moore machine that q₃ is the only state which prints out the character 1, which shows that the moment the state q₃ is entered, the machine will print out 1. To enter the state q₃, starting from q₀, the string must contain bba. It can also be observed that to enter the state q₃ once more, the string must contain another substring bba. In general, the input string will visit the state q₃ as many times as the number of substring bba occurs in the input string. Thus the number of 1's in an output string will be the same as the number of substring bba occurs in the corresponding input string.

📌 Example: Input b b b a b a a b b a a → Output 0 0 0 0 1 0 0 0 0 0 1 0

Mealy machine

A Mealy machine consists of the following:

• A finite set of states q₀, q₁, q₂, ... where q₀ is the initial state.
• An alphabet of letters Σ = {a,b,c,...} from which the input strings are formed.
• An alphabet Γ={x,y,z,...} of output characters from which output strings are generated.
• A pictorial representation with states and directed edges labeled by an input letter along with an output character. The directed edges also show how to go from one state to another corresponding to every possible input letter.

⚠️ Note: It is not possible to give a transition table in this case.

💡 Why this matters: Unlike Moore machines where output is associated with states, Mealy machines produce output on transitions, making them more efficient for certain applications.

Note: Similar to Moore machine, in Mealy machine no state is designated to be a final state, so there is no question of accepting any language by Mealy machine. However, in some cases the relation between an input string and the corresponding output string may be identified by the Mealy machine. Moreover, the state to be initial is not important, as if the machine is used several times and is restarted after some time, the machine will be started from the state where it was left off.

Example

Consider the Mealy machine having the states q₀, q₁, q₂, q₃, where q₀ is the start state and Σ = {a,b}, Γ={0,1}. Running the string abbabbba over the machine, the corresponding output string will be 11011010.

It may be noted that in Mealy machine, the length of output string is equal to that of input string.

📌 Example: Input a b b a b b b a → Output 0 1 1 1 1 0 1 0

Example

Consider the Mealy machine having the states q₀, q₁, q₂, where q₀ is the start state and Σ = {a,b}, Γ={0,1}. It is observed that if in the output string the nth character is 1, it shows that the nth letter in the input string is the second in the pair of double letter. For babaababba as input string the machine will print 0000100010.

Example

Consider the Mealy machine having the only state q₀ as the start state and Σ = {0,1}, Γ= {0,1} with transitions 0/1, 1/0. If 0011010 is run on this machine then the corresponding output string will be 1100101. This machine is called Complementing machine.

Constructing the incrementing machine

In the previous example of complementing machine, it has been observed that the input string and the corresponding output string are 1's complement of each other. There is a question whether the Mealy machine can be constructed so that the output string is increased, in magnitude, by 1 than the corresponding input string? The answer is yes. This machine is called the incrementing machine.

Before constructing the incrementing machine, consider how 1 is added to a binary number. Since if two numbers are added, the addition is performed from right to left, so while increasing the binary number by 1, the string (binary number) must be read by the corresponding Mealy machine from right to left, and hence the output string (binary number) will also be generated from right to left.

Consider the following additions: a) 100101110 + 1 = 100101111 b) 1001100111 + 1 = 1001101000

It may be observed that:

• If the rightmost bit of binary number to be incremented is 0, the output binary number can be obtained by converting the rightmost bit to 1 and remaining bits unchanged.
• If the rightmost bit of binary number is 1, then the output can be obtained by converting that 1 along with all its concatenated 1's to 0's, then converting the next 0 to 1 and remaining bits unchanged.

The observations help to construct the Incrementing (Mealy) machine. The Mealy machine has the states q₀, q₁, q₂, where q₀ is the start state and Σ = {0,1}, Γ={0,1}.

It may be observed that, in the incrementing machine, if 0 is read at initial state q₀, that 0 is converted to 1 and a no change state q₁ (no carry state) is entered where all 0's and all 1's remain unchanged. If 1 is read at initial state, that 1 is converted to 0 and the state q₂ (owe carry state) is entered, where all 1's are converted to 0's and at that state if 0 is read, that 0 is converted to 1 and the machine goes to no change state.

📌 Example: If the strings 100101110 and 1001100111 are run over this machine, the corresponding output strings will be 100101111 and 1001101000 respectively.

Note: It is to be noted that if the string 111111 is run over the incrementing machine, the machine will print out 000000, which is not increased in magnitude by 1. Such a situation is called an overflow situation, as the length of output string will be the same as that of input string.

💡 Why this matters: The overflow situation demonstrates a fundamental limitation — the machine cannot represent a carry beyond the most significant bit because input and output strings must have equal length.

It may also be noted that there exists another incrementing machine with two states.

⭐ Key Takeaways

The most critical points to remember are: (1) In a Moore machine, output is associated with states (each state prints a character when entered), while in a Mealy machine, output is associated with transitions (each edge is labeled with input/output). (2) The number of 1's in the output of the given Moore machine equals the number of occurrences of substring "bba" in the input, demonstrating how Moore machines can count pattern occurrences. (3) Mealy machines always produce an output string of the same length as the input string, and no state is designated as final. (4) The complementing machine is a simple one-state Mealy machine that inverts each bit (0→1, 1→0). (5) The incrementing machine reads binary numbers from right to left and adds 1, handling carries through states q₁ (no carry) and q₂ (owe carry), but suffers from overflow when the input is all 1's.

🧠 Quick Revision Questions

1. What is the fundamental difference between how Moore machines and Mealy machines associate output with input?
2. In the example Moore machine, what substring must occur in the input for the machine to output a 1, and why?
3. For the incrementing machine, why must the input be read from right to left rather than left to right?
4. What happens when the string "111111" is run on the incrementing machine, and what is this situation called?
5. In the Mealy machine example with states q₀, q₁, q₂ (where nth output character 1 indicates double letter), what would the output be for input string "aabbaa"?

📘 Lecture 22 — Applications of complementing and incrementing machines, Equivalent machines, Moore equivalent to Mealy, proof, example, Mealy equivalent to Moore, proof, example

📖 Overview: This lecture demonstrates practical applications of Mealy machines, specifically how complementing and incrementing machines can be used for binary subtraction. It then formally defines machine equivalence and provides rigorous proofs with examples for converting between Moore and Mealy machine types, establishing their fundamental relationship in automata theory.

🗂️ Topics Covered

The lecture covers applications of complementing and incrementing machines for binary subtraction, followed by the definition of equivalent machines. It then presents the theorem and proof for converting Moore machines to equivalent Mealy machines with a detailed example, and similarly proves the conversion from Mealy to Moore machines with an illustrative example, including state splitting when necessary.

📝 Lecture Summary

Applications of Incrementing and Complementing machines

1’s complementing and incrementing machines, which are essentially Mealy machines, are highly useful in computing. The incrementing machine helps build a machine that can perform addition of binary numbers. Using the complementing machine together with the incrementing machine, one can build a machine that performs subtraction of binary numbers.

Method to subtract a binary number b from a binary number a:

1. Add the 1’s complement of b to a (ignoring the overflow, if any)
2. Increase the result, in magnitude, by 1 using the incrementing machine (ignoring the overflow if any)

Note: If there is no overflow in step (1), take 1’s complement once again in step (2) instead. This occurs when b is greater than a in magnitude.

📌 Example: Subtract binary number 101 from binary number 1110. Let a = 1110 and b = 101 = 0101 (digits of b are equated with that of a)

Step 1: Adding 1’s complement (1010) of b to a: 1110 +1010

11000 → ignoring overflow gives 1000

Step 2: Using the incrementing machine, increase result 1000 by 1: 1000 +1

1001 (same as ordinary subtraction)

💡 Why this matters: This method can also be applied to decimal subtraction with the change that 9’s complement of b is added to a in step (1).

Equivalent machines

Two machines are said to be equivalent if they print the same output string when the same input string is run on them.

Remark: Two Moore machines may be equivalent. Similarly, two Mealy machines may be equivalent. However, a Moore machine cannot be equivalent to any Mealy machine directly. But ignoring the extra character printed by the Moore machine, there exists a Mealy machine which is equivalent to the Moore machine.

Theorem — Moore equivalent to Mealy

Statement: For every Moore machine there is a Mealy machine that is equivalent to it (ignoring the extra character printed by the Moore machine).

Proof: Let M be a Moore machine. Shifting the output characters corresponding to each state to the labels of corresponding incoming transitions yields a Mealy machine equivalent to M.

Note: While converting a Moore machine into an equivalent Mealy machine, the output character of a state is ignored if there is no incoming transition at that state. A loop at a state is also considered an incoming transition.

📌 Example: Consider the following Moore machine with states q0/0, q1/1, q2/0, q3/1 and transitions on a and b.

Using the method above, the equivalent Mealy machine is obtained. Running the string abbabbba on both machines:

Theorem — Mealy equivalent to Moore

Statement: For every Mealy machine there is a Moore machine that is equivalent to it (ignoring the extra character printed by the Moore machine).

Proof: Let M be a Mealy machine. At each state, there are two possibilities for incoming transitions:

• Same output character: Shift that character to the corresponding state.
• Different output characters: The state is converted to as many states as the number of different output characters. If at state qi there are transitions with two output characters, then qi is split into qi¹ for one character and qi² for the other. These new states should behave like qi as well.

Note: If there is no incoming transition at a state, any output character may be associated with that state. If the initial state is converted into more than one new state, only one of these new states is considered the initial state.

📌 Example: Consider a Mealy machine with states q0, q1, q2, q3 and transitions labeled with outputs.

The conversion process involves:

1. Shifting output character 1 of transition b to q0
2. Shifting output character 0 of transition a to q1
3. Shifting output character 1 of transition b to q2
4. Splitting q3 into q3¹ and q3²

Running the string abbabbba on both machines:

⭐ Key Takeaways

The complementing and incrementing machines provide a practical method for binary subtraction by combining 1's complement addition with an increment operation. Machine equivalence is defined by identical output strings for the same input, but Moore and Mealy machines cannot be directly equivalent due to Moore's extra output character. The conversion from Moore to Mealy involves shifting state outputs to incoming transition labels while ignoring states with no incoming transitions. The reverse conversion from Mealy to Moore requires splitting states when incoming transitions have different output characters, with each new state inheriting the behavior and one output character of the original state. These conversion theorems establish that despite their structural differences, Moore and Mealy machines are equivalent in computational power when the initial extra character is disregarded.

🧠 Quick Revision Questions

1. How do you subtract binary number b from binary number a using the complementing and incrementing machines, and what special case requires an alternative step?
2. What is the formal definition of equivalent machines, and why can't a Moore machine be directly equivalent to a Mealy machine?
3. In the Moore-to-Mealy conversion, what happens to the output of a state that has no incoming transitions?
4. In the Mealy-to-Moore conversion, what procedure is followed when a state has incoming transitions with different output characters?
5. When the initial state of a Mealy machine is split into multiple states during conversion to Moore, how is the new initial state determined?