Mastering Deterministic Finite Automata: Construction & Core Concepts

DFA for Strings with Odd 'a's and Even 'b's

This section details the construction of a Deterministic Finite Automaton (DFA) to accept strings composed of 'a's and 'b's, specifically those with an odd number of 'a's and an even number of 'b's.

Language Characteristics:

• Odd number of 'a's: At least one 'a', and the total count must be odd.
• Even number of 'b's: At least zero 'b's, and the total count must be even.

Examples of String Acceptance:

Let L be the language of accepted strings.

• abbaabbaabb → Reject (Odd 'a's, Odd 'b's)
• aabaabaab → Reject (Even 'a's, Odd 'b's)
• ababab → Reject (Even 'a's, Odd 'b's)
• bababa → Reject (Even 'a's, Odd 'b's)
• bbaaabbaaabbaaa → Accept (Odd 'a's, Even 'b's)
• aaabbaaabbaaabb → Accept (Odd 'a's, Even 'b's)

DFA for Decimal Strings Divisible by 3

This section outlines the steps to draw a DFA that accepts decimal strings (numbers) which are divisible by 3.

Step 1: Define Parameters

• Radix (Base): 10 (Decimal system)
• Input Alphabet (Σ): {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
• Divisor (k): 3

Step 2: Determine Possible Remainders & States

• Possible Remainders: {0, 1, 2} (when dividing by 3)
• States (Q): {q₀, q₁, q₂} (each state corresponds to a remainder)

Step 3: Group Digits by Remainder

Digits 0-9 are grouped based on their remainder when divided by 3:

• 0, 3, 6, 9 → S(0) (Remainder 0)
• 1, 4, 7 → S(1) (Remainder 1)
• 2, 5, 8 → S(2) (Remainder 2)

Remainder Calculation Examples:

• Remainder of 0 when divided by 3 is 0
• Remainder of 1 when divided by 3 is 1
• Remainder of 2 when divided by 3 is 2

Fundamental Concepts in Automata Theory

This section defines key terms essential for understanding formal languages and automata.

i) Alphabet (Σ)

• A finite, non-empty set of symbols (characters).
• Denoted by Σ (Sigma).
• These symbols are the building blocks for constructing strings.
• Symbols in an alphabet can be letters, digits, or special characters.

Examples:

• Σ = {a, b}
• Σ = {0, 1, 2, 3}
• Σ = {x, y, z}

ii) Power of an Alphabet (Σ^k)

• Represented as Σ^k, this is the set of all strings of a specific length k formed using symbols from the alphabet Σ.
• Σ⁰: Contains only the empty string (ε), which has a length of 0.
• Σ¹: Contains all strings of length 1 (i.e., the alphabet itself).

Examples (for Σ = {a, b}):

• Σ⁰ = {ε}
• Σ¹ = {a, b}
• Σ² = {aa, ab, ba, bb}

Kleene Star (Σ*) and Kleene Plus (Σ⁺):

• Σ* = Σ⁰ ∪ Σ¹ ∪ Σ² ∪ Σ³ ∪ ... ∪ Σⁿ ∪ ... (Includes the empty string)
• Σ⁺ = Σ¹ ∪ Σ² ∪ Σ³ ∪ ... ∪ Σⁿ ∪ ... (Excludes the empty string)

iii) Languages

• A finite or infinite set of strings over a finite alphabet Σ*.
• Any subset of Σ* can be considered a language.
• Formal languages often have specific rules that determine which strings are included in the subset.

Example:

Let Σ = {a, b}.

L = { w ∈ Σ* | w begins with 'b' }

This implies L = { b, ba, bb, baa, bab, bba, bbb, ... }

iv) String

• A finite sequence of characters or symbols chosen from a specific alphabet (Σ).
• Strings are the basic building blocks of languages.

Example:

Given Σ = {a, b}, valid strings include: a, b, aa, ab, ba, bb, etc.

Deterministic Finite Automata (DFA): Definition & Notations

A Deterministic Finite Automaton (DFA) is a mathematical model of computation that consists of a finite set of states and transitions between those states based on input symbols.

Formal Definition of a DFA

A DFA is formally defined as a 5-tuple M = (Q, Σ, δ, q₀, F), where:

• Q: A finite set of states.
• Σ: A finite set of input symbols (the alphabet).
• δ: The transition function, mapping (Q × Σ) to Q. This function defines the next state for each current state and input symbol.
• q₀ ∈ Q: The initial (start) state.
• F ⊆ Q: The set of accepting (final) states.

Preferred Notations for Describing the Transition Function

1. Transition Diagram (State Diagram)

• A graphical representation that shows states as nodes and transitions as directed edges labeled with input symbols.
• It visually depicts how the DFA moves from one state to another based on input.

NFA to DFA Conversion: Lazy Evaluation Method

This section demonstrates the process of converting a Non-deterministic Finite Automaton (NFA) into an equivalent Deterministic Finite Automaton (DFA) using the lazy evaluation method.