Theory of Computation - DFA Construction and Language Regularity

General Topics in TOC Syllabus:
- Finite Automaton & Regular Languages.
- Pushdown Automata (PDA) & Context-Free Languages (CFL).
- Turing Machine & Recursive Enumerable Languages.
- Undecidability.
Recommended Textbooks:
- 1. Peter Linz.
- 2. Michael Sipser.
- 3. Hopcroft & Ullman.

Key topics reviewed:
- Alphabets ( $\Sigma$ ), Strings ( $w$ ), and Languages ( $L$ ).
- DFA acceptance methods.
- Previous Year Questions (PYQs).
Current Core Concepts:
- Converting a DFA to its corresponding Language ( $DFA \rightarrow Language$ ).
- Converting a Language description into a DFA ( $Language \rightarrow DFA$ ).

Case Study 1: String Property Extraction
- A DFA is presented with transitions for 0s and 1s.
- The structure shows a sequential path for zeros: $q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2 \xrightarrow{0} q_3 \xrightarrow{0} q_4 \xrightarrow{0} \text{Dead State}$ .
- This implies a requirement for exactly 4 zeros.
- For 1s, the final state is reached after a specific count of 1s.
- Conclusion: The language accepted is the set of all strings containing exactly 4 zeros and at least two ones ( $L = \{w \mid \#0(w) = 4 \text{ and } \#1(w) \geq 2\}$ ).

Problem: Determine the number of binary strings of length $n$ accepted by the given finite automata.
Automata Description:
- $\Sigma = \{0, 1\}$ .
- The DFA accepts strings starting with 1.
- Any string starting with 0 goes to a dead state.
Mathematical Calculation:
- If the length of the string is $n$ , the first bit is fixed (must be 1).
- The remaining $(n - 1)$ positions can be either 0 or 1.
- Total binary strings of length $n$ starting with 1 is calculated as: $1 \times 2 \times 2 \times \dots \times 2 = 2^{n-1}$ .
Results for specific $n$ :
- For $n = 2$ : Strings are $\{10, 11\}$ , count is $2^{2-1} = 2$ .
- For $n = 3$ : Strings are $\{100, 101, 110, 111\}$ , count is $2^{3-1} = 4$ .
- For $n = 4$ : Count is $2^{4-1} = 8$ .
Final Answer: The number of strings of length $n$ is $\{2^{n-1} \mid n \geq 1\}$ .

Main Principle: A DFA is not possible if there is a comparison (dependency) between the counts of different symbols in the language string.
Dependency vs. Independence:
- Dependency exist: If symbols must be compared (e.g., $n = m$ , $n > m$ ), a DFA is NOT possible because finite automata have no memory to store and compare arbitrary counts.
- No Dependency: If the powers/counts are unrelated (e.g., $n, m \geq 0$ ), a DFA IS possible.
Analysis of Specific Languages:
- $L_1 = \{a^n b^m \mid n > m\}$ : DFA not possible (requires comparison).
- $L_2 = \{a^n b^n \mid n \geq 1\}$ : DFA not possible (requires exact counting/comparison).
- $L_3 = \{a^n b^m \mid n, m \geq 0\}$ : DFA possible (no comparison; independent).
- $L = \{a^n b^m c^{n+m} \mid n, m \geq 1\}$ : DFA not possible (requires adding $n$ and $m$ then comparing to $c$ 's count).
- $L = \{a^n b^{2m} \mid n, m \geq 1\}$ : DFA possible (while it looks complex, $n$ and $m$ are independent; the DFA only needs to track that $b$ 's are even).
- $L = \{a^n b^m \mid n \neq m\}$ : DFA not possible (requires comparison).

Example 1: $L = \{a^n b^m \mid n, m \geq 1\}$
- Logic: Must have at least one 'a', then at least one 'b'. After 'b' begins, no more 'a's are allowed.
- States needed: 4 states minimum.
  - $q_0$ : Start state.
  - $q_1$ : Received at least one 'a'.
  - $q_2$ : Received at least one 'b' (Final state).
  - $q_3$ : Dead State (for 'b' before 'a', or 'a' after 'b').
Example 2: $L = \{a^n b^m \mid n \geq 1, m \geq 0\}$
- Logic: Must start with at least one 'a'. Can have any number of 'b's (including zero).
- States needed: 3 states.
  - $q_0$ : Start state.
  - $q_1$ : Received at least one 'a' (Final State).
  - $q_2$ : Dead state (for starting with 'b').
Example 3: $L = \{a^n b^m \mid n \geq 0, m \geq 0\}$
- Logic: Any number of 'a's followed by any number of 'b's.
- State count: 3 states (Start is final, transition to 'b' loop state, dead state for 'a' after 'b').

Question: Which of the following are regular sets?
- 1. $\text{S}_1 = \{a^n b^{2m} \mid n \geq 0, m \geq 0\}$ : Regular (No dependency between $n$ and $m$ ).
- 2. $\text{S}_2 = \{a^n b^m \mid n = 2m\}$ : Not Regular (Dependency exists; must compare counts).
- 3. $\text{S}_3 = \{a^n b^m \mid n \neq m\}$ : Not Regular (Dependency exists).
- 4. $\text{S}_4 = \{xcy \mid x, y \in \{a, b\}^* \}$ : Regular (The center 'c' is just a marker; $x$ and $y$ have no dependency on each other).

Q: How can we tell if $L = \{a^n b^{2m}\}$ is regular but $L = \{a^n b^n\}$ is not?
A: In the first case, the variables $n$ and $m$ are entirely independent. The DFA simply checks for a sequence of 'a's followed by an even number of 'b's. This uses finite memory (parity check). In the second case, the machine must remember the exact count of 'a's to ensure the 'b's match. Since the count of 'a's can be infinite, a finite state machine (DFA) cannot perform this task.