Theory of Computation Lecture 3

Formal Definition of Computation

• A finite automaton M is defined as a 5-tuple: M = (Q, Σ, δ, q0, F).
• A string w = w1w2...wn consists of symbols from the alphabet Σ.
• M accepts w if there exists a sequence of states r0, r1,..., rn in Q meeting three conditions:
  • r0 is the initial state q0.
  • Transition δ(r_i, w_{i+1}) leads to r_{i+1} for i = 0,..., n-1.
  • The final state rn must be in the set of accepting states F.
• M recognizes language A defined as A = {w | M accepts w}.

Designing Finite Automata

• To design a finite automaton to recognize strings with an odd number of 1s:
  • Track whether the count of 1s so far is even or odd instead of remembering the entire string.
  • Transition states are defined as:
    • State q_even (even number of 1s).
    • State q_odd (odd number of 1s).
  • On reading a 1, transition from q_even to q_odd, and vice versa. Reading a 0 retains the current state.
• The start state for the automaton is q_even, accepting state is q_odd (as it represents odd occurrences).

Example of Recognizing Substrings

• A finite automaton E2 for recognizing the pattern "001":
  • Represents four states based on the substring seen:
    • q (no symbols seen).
    • q0 (one 0 seen).
    • q00 (two 0s seen).
    • q001 (substring "001" seen).
  • Transition rules:
    • From q, stay in q for 1, move to q0 for 0.
    • From q0, move to q for 1, go to q00 for 0.
    • From q00, move to q001 for 1, stay in q00 for 0.
    • In q001, remain in q001 for any input.
  • The start state is q, and only the state q001 is accepting.

Regular Operations on Languages

• Union: Combines strings from two languages A and B into one language.
• Concatenation: Attaches strings from A in front of strings from B producing new strings in the resulting language.
• Star Operation: A unary operation applied to a single language A, concatenating any number of strings in A to create new strings in the language. The empty string "" is always included in A*.
• Example with the alphabet {a, b, ..., z}:
  • A = {good, bad} and B = {boy, girl} results in:
    • Union: A ∪ B = {good, bad, boy, girl}
    • Concatenation: A ∩ B = {goodboy, goodgirl, badboy, badgirl}
    • Star: A* = {", good, bad, goodgood, badbad,...}