Ch 1: Regular Languages

• A finite automaton is a mathematical model used to represent and analyze systems that exhibit a finite number of states, transitions between these states, and responses to external inputs.
• A finite automaton is a 5-tuple (Q, Σ, δ, q0, F), where

  1. Q is a finite set called the states,
  2. Σ is a finite set called the alphabet,
  3. δ : Q × Σ−→Q is the transition function,
  4. q0 ∈ Q is the start state, and
  5. F ⊆ Q is the set of accept states.
• If a machine accepts no strings, it still recognizes one language— namely, the empty language ∅.
• A language is called a regular language if some finite automaton recognizes it.
• What are regular operations?

  Operations that can be performed on regular languages, such as union, concatenation, and star.
• Let A and B be languages. We define the regular operations union, concatenation, and star as follows:

  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}.
• A collection of objects is closed under some operation if applying that operation to members of the collection returns an object still in the collection
• The closure property says that any operation applied to two regular languages produces another regular language.
• When the machine is in a given state and reads the next input symbol, we know what the next state will be—it is determined. We call this deterministic computation.
• In a nondeterministic machine, several choices may exist for the next state at any point.
• Every DFA is automatically a NFA.
• A nondeterministic finite automaton is a 5-tuple (Q, Σ, δ, q0, F), where

  1. Q is a finite set of states,
  2. Σ is a finite alphabet,
  3. δ : Q × Σε−→P(Q) is the transition function,
  4. q0 ∈ Q is the start state, and
  5. F ⊆ Q is the set of accept states.
• Two machines are equivalent if they accept the same language.
• A language is regular if and only if some nondeterministic finite automaton recognizes it.
• Regular expressions are algebraic descriptions of regular languages.
• The language of a regular expression is the set of all strings that match the pattern.
• Say that R is a regular expression if R is:

  1. a for some a in the alphabet Σ,
  2. ε,
  3. ∅,
  4. (R1 ∪ R2), where R1 and R2 are regular expressions,
  5. (R1 ◦ R2), where R1 and R2 are regular expressions, or
  6. ($R^*$$_1$), where R1 is a regular expression.
• ε represents the language containing a single string—namely, the empty string
• ∅ represents the language that doesn’t contain any strings.
• $Σ ^∗1Σ ^∗ =$


  {w | w has at least one 1}
• $0^*$$10^*$$=$


  {w | w contains a single 1}
• $Σ ^∗001Σ^ ∗ =$


  {w | w contains the string 001 as a substring}
• $1^ ∗ (01^+ ) ^∗ =$


  = {w | every 0 in w is followed by at least one 1}
• $(ΣΣ)^∗ =$


  {w | w is a string of even length}
• $(ΣΣΣ)^∗ =$


  {w | the length of w is a multiple of 3}
• $01 ∪ 10 =$


  {01, 10}
• $0Σ ^∗0 ∪ 1Σ ^∗1 ∪ 0 ∪ 1 =$


  {w | w starts and ends with the same symbol}
• $(0 ∪ ε)(1 ∪ ε) =$


  {ε, 0, 1, 01}
• $1 ∗∅ =$$∅$


  Concatenating the empty set to any set yields the empty set.
• The length of a string is the number of symbols that it contains.
• To convert a DFA into a equivalent regular expression, we first must convert it into a GNFA.
• A generalized nondeterministic finite automaton is a 5-tuple,

  $(Q, Σ, δ, q, qstart, qaccept)$, where

  1. . Q is the finite set of states,
  2. Σ is the input alphabet,
  3. δ : (Q - {qaccept}) * (Q - {qstart}) -> R is the transition function,
  4. qstart is the start state,
  5. qaccept is the accept state
• The pumping lemma is a proof that proves a specific language is not regular.
• The pumping length is the number of states in the smallest finite state machine for the language.
• Pumping Lemma Theorem:

  If A is a regular language, then there is number p where if s is any string in A of length at least p, then s may be divided into three pieces, s = xyz, satisfying the following conditions:

  1. for each $i ≥ 0, xy^iz ∈ A$
  2. $|y| > 0$, and
  3. $|xy| ≤ p$