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,...}

Explore the formal definitions and mathematical concepts underlying finite automata in this lecture. Gain insights into the structure of computation as defined in theoretical computer science. This quiz tests your understanding of the formal mechanisms that govern computation.