CISC3007 Formal Language and Automata

Why Automata Theory?

Automata theory is for the study of abstract computing devices. The main characters are Finite State Machines.

Part 1. Basic Concepts

1.1 Alphabets

Definition of Alphabets:

• An alphabet is defined as a finite set of symbols.
• Denotion: "Σ";
• e.g., Σ={0,1} is a binary alphabet, Σ={a,b,c,...z} is an alphabet of the English language.

1.2 Strings

Definition of Strings:

• A string is a finite sequence over an alphabet Σ.
• Empty string is denoted by {ε} (pronounced epsilon).
• e.g., 0011,01,0101,... are strings over alphabet Σ={0,1}.

1.2.1 String Operations:

A. Length: |0010| = 4, |1101110| = 7, |ε| = 0;

B. Substrings:

• B-1. Prefix: aaabc, aaabc, aaabc;
• B-2. Suffix: aaabc, aaabc, aaabc;
• B-3. Substring: aaabc;

C. Multiple Strings:

• C-1. Concatenation: α = abd, β = ce → αβ = abdce;
• C-2. Exponentiation: α = abd → α^3= abdabdabd;
• C-3. Reversal: α = abd → a^R = dba;

D. Alphabets:

• D-1. Power of an Alphabet: Σ^k = set of all k-length strings formed by symbols in Σ.
  • e.g., Σ = {a,b}, Σ^2 = {aa,ab,ba,bb}.
• D-2. Kleen Closure: Σ* = Σ^0 ∪ Σ^1 ∪ Σ^2 ∪ ...
• D-3. Kleen Plus: Σ+ = Σ^1 ∪ Σ^2 ∪ Σ^3 ...
  • Note that Σ* = Σ+ ∪ Σ^0 = Σ+ ∪ {ε}.

1.3 Languages

Definition of Languages:

• A language is a set of strings over an alphabet.
• A language (basically a set) does not have to be finite.
• e.g.:
  • The set of all English words is a language over the alphabet Σ={a,b,c,....,z}.
  • The set {ε} is a language over ANY alphabet.
  • L1 = {0^n1^n|n>=0} is a language over Σ={0,1}.
  • ...

Part 2. Finite State Machines (Finite Automata)

Finite state machines (i.e. Finite Automata) is used to determine wherther a string meets a requirement.

It takes a string as an input. If the finite state machine reaches a final state, it accepts the string; otherwise it rejects the string.

2.1 Deterministic Finite Automata (DFA)

Definition of a DFA:

A DFA is defined as a quintuple (Q, Σ, δ, q, F) where:

Component	Interpretation
Q	A finite set of states.
Σ	A finite set of input symbols (an alphabet).
δ	Translation function, mapping Q x Σ → Q. i.e., A state takes an input, transmitting to another state.
q0	Unique initial state.
F	A set of final states.