GCUF CSI406 BSCS Theory of Automata Complete Notes with Examples

Definition

A language is a set of strings formed from symbols of a finite alphabet (Σ).

Explanation

An alphabet is a finite set of symbols. A string is a finite sequence of those symbols. The empty string is denoted by ε. A language can be finite or infinite.

Example

Σ = {0, 1}
Language L = {ε, 0, 1, 00, 01, 10, 11, ...} (all possible binary strings).

Definition

A Regular Expression is a notation used to describe regular languages using union, concatenation and Kleene star.

Explanation

It uses operations like + (union), juxtaposition (concatenation), and * (Kleene star) to define patterns for strings.

Example

(a + b)* → All strings over {a, b} including empty string.
0(0 + 1)* → All binary strings starting with 0.

Definition of Finite Automata (FA)

A Finite Automaton is a 5-tuple (Q, Σ, δ, q₀, F) that accepts or rejects strings.

Explanation

DFA has one transition per input. NFA can have multiple or ε-transitions. Transition Graph (TG) is its pictorial form.

Example

DFA for even number of 1s: States Even (start & accept) and Odd. On 1, state changes; on 0, state stays.

Kleene’s Theorem

Definition: Regular languages, Regular expressions and Finite Automata are equivalent.

Example: Any RE can be converted to FA and vice versa.

Transducers

Automata that produce output (Mealy and Moore machines).

Pumping Lemma

Definition: Long strings in regular languages can be pumped while staying in the language.

Example: {0ⁿ1ⁿ | n ≥ 0} is not regular (pumping breaks equality).

Context Free Grammars (CFG)

Definition: A 4-tuple (V, Σ, P, S) with production rules.

Example: Palindromes: S → aSa | bSb | ε

Derivations, Derivation Trees and Ambiguity

Leftmost/rightmost derivations and grammars with multiple parse trees (ambiguous).

Simplifying CFLs and Normal Forms

Chomsky Normal Form (CNF) and Greibach Normal Form (GNF).

Pushdown Automata (PDA)

Stack-based machine that accepts Context Free Languages.

Turing Machines (TM)

Definition: A 7-tuple model with infinite tape that can simulate any computation.

Example: TM that accepts {0ⁿ1ⁿ | n ≥ 0} or adds numbers.

Variations, Universal TM and TM Encoding

Multi-tape, Non-deterministic TM, and Universal TM (simulates any TM).

Context Sensitive Grammars and Chomsky’s Hierarchy

Type-0 Unrestricted, Type-1 Context Sensitive, Type-2 Context Free, Type-3 Regular.

Defining Computers by Turing Machines

TMs define what is computable (Decidability) and what is not.