Back to Subject

Practice MCQ Subjective

Unit 1 - Notes

CSE322 7 min read

Unit 1: FINITE AUTOMATA

1. Basics of Strings and Alphabets

Before defining automata, it is essential to understand the mathematical notations regarding data representation.

Key Definitions

Symbol: An atomic unit of data (e.g., a character, a digit).
Alphabet ( $\Sigma$ ): A finite, non-empty set of symbols.
- Examples: $\Sigma = \{0, 1\}$ (binary), $\Sigma = \{a, b, c\}$ (letters).
String (or Word): A finite sequence of symbols chosen from some alphabet.
- Example: If $\Sigma = \{0, 1\}$ , then $01101$ is a string.
Length of a String ( $|w|$ ): The number of symbols in the string.
- If $w = abc$ , then $|w| = 3$ .
Empty String ( $\epsilon$ or $\lambda$ ): A string with zero occurrences of symbols.
- $|\epsilon| = 0$ .
- Identity property: $w\epsilon = \epsilon w = w$ .

Powers of an Alphabet

$\Sigma^k$ : The set of all strings of length $k$ over $\Sigma$ .
$\Sigma^0 = \{\epsilon\}$ .
$\Sigma^1 = \Sigma$ .

Kleene Star and Positive Closure

Kleene Star ( $\Sigma^*$ ): The set of all possible strings over an alphabet $\Sigma$ , including $\epsilon$ .
$\Sigma^* = \bigcup_{k=0}^{\infty} \Sigma^k = \Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \dots$
Positive Closure ( $\Sigma^+$ ): The set of all possible strings over $\Sigma$ , excluding $\epsilon$ (unless $\epsilon$ is explicitly in $\Sigma$ ).
$\Sigma^+ = \bigcup_{k=1}^{\infty} \Sigma^k = \Sigma^* - \{\epsilon\}$

Language ( $L$ )

A Language is a subset of $\Sigma^*$ . It is a set of strings chosen from $\Sigma^*$ .

Finite Language: $L = \{ab, aa, baa\}$ .
Infinite Language: $L = \{ a^n b^n \mid n \ge 1 \}$ .

2. Definition and Description of a Finite Automaton

A Finite Automaton (FA) is the simplest abstract computational model. It has a limited amount of memory (states). It processes an input string symbol by symbol and changes its state accordingly.

Components of an FA

Input Tape: A linear tape containing the input string.
Read Head: Reads one symbol at a time from left to right.
Finite Control: Determines the next state based on the current state and the input symbol.

Types of Finite Automata

Deterministic Finite Automaton (DFA)
Non-deterministic Finite Automaton (NDFA / NFA)
NFA with $\epsilon$ -moves ( $\epsilon$ -NFA)

3. Transition Systems and Transition Graphs

A Transition System (or Transition Graph) is a diagrammatic representation of an FA.

Graph Components

Vertices (Nodes): Represent the States.
- Start State: Indicated by an incoming arrow from nowhere.
- Final (Accepting) State: Indicated by double circles.
- Non-final State: Single circle.
Edges (Arcs): Represent Transitions.
- Directed edges labeled with input symbols.
- An edge from state $q_1$ to $q_2$ labeled $a$ means: "If in state $q_1$ and input is $a$ , go to $q_2$ ."

4. Deterministic Finite Automata (DFA)

A DFA is "deterministic" because for every state and every input symbol, there is exactly one specific next state.

Formal Definition

A DFA is a 5-tuple $M = (Q, \Sigma, \delta, q_0, F)$ where:

$Q$ : A finite set of states.
$\Sigma$ : A finite set of input symbols (alphabet).
$\delta$ : A transition function (mapping).
$q_0$ : The initial (start) state ( $q_0 \in Q$ ).
$F$ : A set of accepting (final) states ( $F \subseteq Q$ ).

Properties of Transition Functions in DFA

The transition function is defined as:

\delta: Q \times \Sigma \rightarrow Q

Total Function: $\delta$ must be defined for every pair $(q, a)$ where $q \in Q$ and $a \in \Sigma$ .
Single Value: The result is exactly one state.

Extended Transition Function ( $\hat{\delta}$ )

To describe the processing of a string $w$ rather than a single symbol, we define $\hat{\delta}: Q \times \Sigma^* \rightarrow Q$ recursively:

Base Case: $\hat{\delta}(q, \epsilon) = q$ (Processing an empty string leaves the state unchanged).
Recursive Step: For string $w = xa$ (where $x$ is a string and $a$ is a symbol):
$\hat{\delta}(q, xa) = \delta(\hat{\delta}(q, x), a)$

Acceptability of a String by DFA

A string $w$ is accepted by a DFA $M = (Q, \Sigma, \delta, q_0, F)$ if and only if:

\hat{\delta}(q_0, w) \in F

Meaning: After processing the entire string starting from

q_0

, the automaton halts in a final state. If it halts in a non-final state, the string is rejected.

5. Non-deterministic Finite Automata (NDFA/NFA)

An NFA allows flexibility in transitions. From a specific state on a specific input, the machine may go to multiple states, one state, or no state at all.

Formal Definition

An NFA is a 5-tuple $M = (Q, \Sigma, \delta, q_0, F)$ where:

$Q, \Sigma, q_0, F$ are defined exactly as in a DFA.
$\delta$ (Transition Function): $Q \times \Sigma \rightarrow 2^Q$ (Power set of Q).

Properties of Transition Functions in NFA

The output of $\delta(q, a)$ is a set of states (subset of $Q$ ).
It allows "guessing" the correct path.

Acceptability of a String by NFA

A string $w$ is accepted by an NFA if there exists at least one sequence of transitions (path) corresponding to $w$ that leads from $q_0$ to some state in $F$ .

6. The Equivalence of DFA and NDFA

Despite NFA appearing more powerful due to non-determinism, DFA and NFA are equivalent in computational power. Both accept the class of Regular Languages.

Theorem

For every NFA $N$ , there exists a DFA $M$ such that $L(M) = L(N)$ .

Subset Construction Algorithm (Conversion NFA $\rightarrow$ DFA)

To convert an NFA to a DFA, we simulate the NFA by tracking the set of states the NFA could be in at any moment.

DFA States ( $Q_D$ ): The power set of the NFA states ( $2^{Q_N}$ ). If NFA has $n$ states, DFA can have up to $2^n$ states.
DFA Start State: $\{q_0\}$ .
DFA Transitions:
For a set of NFA states $\{q_1, q_2, \dots, q_k\}$ and input $a$ :
$\delta_D(\{q_1, \dots, q_k\}, a) = \bigcup_{i=1}^k \delta_N(q_i, a)$
DFA Final States ( $F_D$ ): Any subset of NFA states that contains at least one final state from the NFA.

7. Regular Languages

A language $L$ is called a Regular Language if there exists a Finite Automaton (DFA or NFA) that accepts it.

Properties

Regular languages are closed under:
- Union
- Intersection
- Concatenation
- Kleene Star
- Complementation

8. Finite Automata with Output: Mealy and Moore Machines

Standard FAs are "acceptors" (output is Yes/No). Mealy and Moore machines are "transducers"—they generate an output string based on the input string.

Similarities

Both have states ( $Q$ ), inputs ( $\Sigma$ ), outputs ( $\Delta$ ), transition function ( $\delta$ ), and start state ( $q_0$ ).
No Final States: They run as long as there is input.

Moore Machine

Output depends only on the current state.
Definition: 6-tuple $(Q, \Sigma, \Delta, \delta, \lambda, q_0)$ .
Output Function: $\lambda: Q \rightarrow \Delta$ .
For every state entered, a character is printed.
Note: If input length is $n$ , output length is usually $n+1$ (includes output for initial state).

Mealy Machine

Output depends on the current state AND the current input symbol.
Definition: 6-tuple $(Q, \Sigma, \Delta, \delta, \lambda, q_0)$ .
Output Function: $\lambda: Q \times \Sigma \rightarrow \Delta$ .
Output is generated during the transition.
If input length is $n$ , output length is $n$ .

Equivalence

Moore and Mealy machines are equivalent. Any problem solvable by one is solvable by the other.

Mealy $\to$ Moore: Split states to accommodate outputs associated with incoming transitions.
Moore $\to$ Mealy: Associate the state's output with the incoming transition.

9. Minimization of Finite Automata

Minimization creates a unique DFA with the fewest possible states for a given regular language.

Distinguishable vs. Indistinguishable States

Two states $p$ and $q$ are indistinguishable (equivalent) if, for every possible string $w$ :

is a final state AND is a final state
- OR
$\hat{\delta}(p, w)$ is NOT final AND $\hat{\delta}(q, w)$ is NOT final.

If there exists even one string $w$ that drives $p$ to a final state and $q$ to a non-final state (or vice versa), $p$ and $q$ are distinguishable.

Minimization Algorithm (Table Filling Method / Myhill-Nerode)

Remove Unreachable States: Delete states that cannot be reached from $q_0$ .
Initialize Table: Create a table of all pairs of states $(p, q)$ .
Mark Distinguishable Pairs:
- Mark pair $(p, q)$ if $p \in F$ and $q \notin F$ (or vice versa).
Propagate Marks:
- For every unmarked pair $(p, q)$ and every input symbol $a \in \Sigma$ :
- If the pair of next states $(\delta(p, a), \delta(q, a))$ is already marked, then mark $(p, q)$ .
- Repeat this step until no new changes occur.
Merge:
- All pairs $(p, q)$ that remain unmarked are equivalent. Merge them into a single state in the minimized DFA.

Unit 2

Unit 1 - Notes

Table of Contents

Unit 1: FINITE AUTOMATA

1. Basics of Strings and Alphabets

Key Definitions

Powers of an Alphabet

Kleene Star and Positive Closure

Language ()

2. Definition and Description of a Finite Automaton

Components of an FA

Types of Finite Automata

3. Transition Systems and Transition Graphs

Graph Components

4. Deterministic Finite Automata (DFA)

Formal Definition

Properties of Transition Functions in DFA

Extended Transition Function ()

Acceptability of a String by DFA

5. Non-deterministic Finite Automata (NDFA/NFA)

Formal Definition

Properties of Transition Functions in NFA

Acceptability of a String by NFA

6. The Equivalence of DFA and NDFA

Theorem

Subset Construction Algorithm (Conversion NFA DFA)

7. Regular Languages

Properties

8. Finite Automata with Output: Mealy and Moore Machines

Similarities

Moore Machine

Mealy Machine

Equivalence

9. Minimization of Finite Automata

Distinguishable vs. Indistinguishable States

Minimization Algorithm (Table Filling Method / Myhill-Nerode)

Language ( $L$ )

Extended Transition Function ( $\hat{\delta}$ )

Subset Construction Algorithm (Conversion NFA $\rightarrow$ DFA)