Strings, Languages, and Automata

Strings

• Strings are a finite sequence of characters
• In programming, strings represent a finite sequence of lexical tokens like "<=".
• An empty string contains no characters and is denoted as ε.
• Concatenation joins two strings s and t, written as s.t or simply st.
• For a string v = s.t.u, 's' is the prefix, 'u' is the suffix, and 't' is a substring.
• A string s is a palindrome if it equals its reversal, denoted as sR = s (for example, 'abba').

Formal Languages

• A formal language consists of strings formed from a finite set of symbols Σ.
• For Σ = {0, 1}, a formal language avoiding consecutive 0s could be {ε, 0, 01, 0101, 011, ...}.
• Most formal languages are infinite sets of strings.

Finite Automaton

• A finite automaton is defined by five components: a set of states, an input alphabet, transition rules, a start state, and an accept state.
• Q represents a finite set of states, ∑ is the alphabet, δ: Q × Σ is the transition function, q0 ∈ Q is the start state, and F ⊆ Q is the set of accept states.
• Finite automata can be visually represented using state diagrams.

Examples of Finite Automata

• Example 1 is a finite automaton M1 with states Q = {q1, q2, q3}, alphabet Σ = {0, 1}, start state q1, and accept state F = {q2}.
• The transition function δ for M1 is defined as:
  • δ(q1, 0) = q1, δ(q1, 1) = q2
  • δ(q2, 0) = q3, δ(q2, 1) = q2
  • δ(q3, 0) = q2, δ(q3, 1) = q2
• M1 can be formally described as (Q, Σ, δ, q0, F) = ({q1, q2, q3}, {0, 1}, δ, q1, {q2}).
• A represents the language accepted by M1, denoted as L(M1) = A, or M1 accepts A or recognizes A.
• For example 1, A includes strings with at least one 1, followed by an even number of 0s: {w | w contains at least one 1 and an even number of 0s follow the last 1}.
• Example 2 is a finite automaton M2 = ({q1, q2}, {0, 1}, δ, q1, {q2}), where the transition function δ is:
  • δ(q1, 0) = q1, δ(q1, 1) = q2
  • δ(q2, 0) = q1, δ(q2, 1) = q2
• Example 3 is a finite automaton M3 = ({q1, q2}, {0, 1}, δ, q1, {q1})
• δ is the same as in M2.
• L(M3) = {w | w is the empty string ε or ends in a 0}.
• Example 4 is a finite automaton M4 = ({s, q1, r1, q2, r2}, {a, b}, δ, s, {q1, r1}).
• L(M4) contains strings that start and end with the same symbol: {w | w starts and ends with a or b}.
• More generally, L(M4) = {w | w starts and ends with the same symbol}.
• Example 5 is a finite automaton M5 = ({q0, q1, q2}, {(RESET), 0, 1, 2}, δ, q0, {q0}).
• M5 calculates the sum of numerical inputs, resetting to 0 upon receiving {RESET}.
• L(M5) contains strings where the sum is a multiple of 3.

Formal Definition of Computation

• Given M = (Q, Σ, δ, q0, F) and a string w = w1w2...wn over Σ, M accepts w if there exists a sequence of states r0, r1, ..., rn in Q such that:
  • r0 = q0 and rn ∈ F
  • δ(ri, wi+1) = ri+1 for i = 0, 1, 2, ..., n - 1
• M recognizes language A if A = {w | M accepts w}.
• A language is regular if a finite automaton recognizes it.

Designing Finite Automata

• Given an alphabet {0,1}, a task is to construct a finite automaton E1 that recognizes strings with an odd number of 1s.
• Keeping track of the number of 1s seen while reading the string is a simple strategy. The two states are: qeven (even number of 1s) and qodd (odd number of 1s).
• The transitions of E1 are:
  • E1 flips from qeven to qodd upon encountering a 1.
  • E1 flips from qodd to qeven upon encountering a 1.
  • E1 stays in the same state when reading a 0.
• The start state is qeven, and the accept state is qodd.
• To design a finite automaton E2 that recognizes strings containing the substring 001, consider four states: a start state, having seen 0, having seen 00, and having seen 001.
• E2 loops through the accept state once it sees "001".

The Regular Operations

• In computation theory, languages behave like mathematical numbers.
• Operations on regular languages are called regular operations:
  • Union: A ∪ B = {x | x ∈ A or x ∈ B}
  • Concatenation: A ◦ B = {xy | x ∈ A and y ∈ B}
  • Star: A* = {x1x2...xk | k ≥ 0 and each xi ∈ A}
• Example: Given Σ = {a, b, ..., z}, A = {good, bad}, and B = {boy, girl}:
  • A ∪ B = {good, bad, boy, girl}
  • A ◦ B = {goodboy, goodgirl, badboy, badgirl}
  • A* = {ε, good, bad, goodgood, goodbad, badgood, badbad, goodgoodgood, goodgoodbad, ...}
• The class of regular languages is closed under union.
• M1 recognizes A1 and M2 recognizes A2, M(Q,Σ,δ,q0,F) such that Q = Q1xQ2

Nondeterminism

• A finite automaton is deterministic if the next state is uniquely determined by the input symbol.
• It is nondeterministic when multiple choices exist for an input symbol.
• Nondeterministic Finite Automaton (NFA) is considered a tree of possibilities rooted from the start state.
• Each branching point in the tree corresponds to multiple choices.
• The machine accepts the input if at least one branch ends in an accepting state.
• In an NFA, constructing is easier but sometimes smaller than Deterministic Finite Automata (DFA)..
• The NFA N3 accepts all strings of the form 0k, where k is a multiple of 2 or 3
• The alphabet is unary, containing only one symbol (0)
• ε-arrow or the transition with ε enables N3 to recognize the strings ε, 00, 000, 0000, ..., but not 0 or 00000.
• One NFA accepts all strings ε, a, baba, baa, but not b, bb, babba
• Its start and accept states are the same in the NFA.
• A Nonterministic Finite Automaton is defined as 5-tuple (Q, Σ, δ, q0, F).
• Function δ is Q × Σ』→P(Q), where P(Q) represents the power set of Q.
• The NFA accepts w if it can be divided into y1, y2, ..., ym
• Every yi is a member of Symbol and Q containing a sequence of r0, r1,...,rm such that: r0 = q0 and rm = F.
• ri+1 belongs to the δ(ri, yi+1)

Equivalence of NFAS and DFAS

• Two machines are equivalent if they recognize the same language.
• Every nondeterministic finite automaton has a deterministic finite automaton that recognizes the same language
• Proof idea: the NFA is converted into a DFA that simulates it
• A language is regular if some NFA recognizes it.
• A language is regular if some DFA can recognize it, and any NFA converted into an equivalent DFA
• No arrow points to the state states, these can then be removed

Closure Under the Regular Operations

• The class of regular languages is closed under the union
• In order to prove this take two NFAs, N1 and N2 for A1 and A2, they are then combined into a new NFA
• The class of regular languages is closed under concatenation
• In order to pove this take two NFAs, N1 and N2 for A1 and A2, they are then combine into a new NFA
• The class of regular languages is closed under the star operation
• In order to pov this is proved with a modification of NFA N1 for A1 which is used to recognize A1*

Regular Expressions

• Regular expressions are expressions built on regular operations
• R becomes a regular expression if:
  • a, for the alphabet symbol Σ
  • ε
  • Φ
  • (R1 U R2), R1 and R2 used as regular expressions
  • (R1 o R2), R1 and R2 used as regular expressions
  • (R1*), R1 used as a regular expression
• Other alphabet examples with: Σ = {0,1}
  • 010 = {w/w} has signal one 1}
  • Σ1Σ = {w/w has at least one 1

Equivalence With Finite Automata

• Regular expressions and finite automatons hold equivalent descriptive
• Every expression made can transfer into one automaton
• A language becomes regular of a regularly described expression
• If one language is described by a regular language, it is considered regular
• Proof idea: when converting a regular express R converts into to new NFA