CENG205 - Theory of Computation
Assist. Prof. Dr. Emre ŞATIR
Week 3
Regular Languages
Designing Finite Automata
Whether it be of automaton or artwork, design is a creative process. As such, it cannot be reduced to
a simple recipe or formula.
However, you might find a particular approach helpful when designing various types of automata.
That is, put yourself in the place of the machine you are trying to design and then see how you would
go about performing the machine’s task (“reader as automaton”).
You have to figure out what you need to remember about the string as you are reading it.
Why not simply remember all you have seen? Bear in mind that you are pretending to be a finite
automaton and that this type of machine has only a finite number of states, which means a finite
memory.
Fortunately, for many languages you don’t need to remember the entire input. You need to
remember only certain crucial information which depends on the particular language considered.
Designing Finite Automata
Construct a DFA that accept sets of all strings over {0,1} with an odd number of 1s.
Do you need to remember the entire string seen so far in order to determine whether the number of
1s is odd?
No! Simply remember whether the number of 1s seen so far is even or odd and keep track of this
information as you read new symbols. If you read a 1, flip the answer; but if you read a 0, leave the
answer as is.
Designing Finite Automata
Example: Construct a DFA that accepts set of all strings that starts with ‘0’.
States like ‘C’ are known as “dead” or “trap” state.
Designing Finite Automata
Construct a DFA that accepts sets of all strings over {0,1} of length 2.
L = {00, 01, 10, 11} → finite set
Designing Finite Automata
Construct a DFA that accepts sets of all strings over {0,1} that contain the string “001” as a substring.
Designing Finite Automata
Construct a DFA that accepts any string over {a,b} that does not contain the string “aabb” as a substring in it.
First, we try to design a simpler problem.
Let us construct a DFA that accepts all strings over {a,b} that contains the string “aabb” in it.
Designing Finite Automata
Then, flip the states. final → nonfinal, nonfinal → final
Regular Languages
Definition: A language is regular if some finite automaton recognizes it.
So, if we are able to build a DFA for a particular language, this language is
set to be a regular language.
Regular Languages
Let 𝐵 = 𝑤 𝑤 has an odd number of 1s}
𝐵 is regular.
Let 𝐶 = 𝑤 𝑤 has equal numbers of 0s and 1s}
𝐶 is not regular (we will prove).
Goal: Understand the regular languages
Operations on Regular Languages
Regular operations. Let 𝐴, 𝐵 be languages:
- Union: 𝐴 ∪ 𝐵 = 𝑤 𝑤 ∈ 𝐴 or 𝑤 ∈ 𝐵}
- Concatenation: 𝐴 ∘ 𝐵 = 𝑥𝑦 𝑥 ∈ 𝐴 and 𝑦 ∈ 𝐵} = 𝐴𝐵
- Star: 𝐴∗ = 𝑥1 … 𝑥𝑘 each 𝑥𝑖 ∈ 𝐴 for 𝑘 ≥ 0}
Note: ε ∈ 𝐴∗ always
Example. Let 𝐴 = {good, bad} and 𝐵 = {boy, girl}.
- 𝐴 ∪ 𝐵 = {good, bad, boy, girl}
- 𝐴 ∘ 𝐵 = 𝐴𝐵 = {goodboy, goodgirl, badboy, badgirl}
- 𝐴∗ = {ε, good, bad, goodgood, goodbad, badgood,
badbad, goodgoodgood, goodgoodbad, … }
Operations on Regular Languages
Another Example
Let A={pq, r} and B={t, uv}
A U B = {pq, r, t, uv}
A ∘ B = {pqt, pquv, rt, ruv}
A* = {ε, pq, pq, r, pqpq, pqr, rpq, rr, …}
Closed under …
Let N = {1, 2, 3, . . . } be the set of natural numbers. When we say that N is
closed under multiplication, we mean that for any x and y in N, the product
x × y also is in N. In contrast, N is not closed under division, as 1 and 2 are in N
but 1/2 is not.
Generally speaking, 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.
We show that the collection of regular languages is closed under all three of
the regular operations. We also show that these are useful tools for
manipulating regular languages and understanding the power of finite
automata.
Closure Properties for Regular Languages
Theorem: If 𝐴1 , 𝐴2 are regular languages, so is 𝐴1 ∪ 𝐴2 (closure under ∪)
Proof: …
Theorem: If 𝐴1 , 𝐴2 are regular languages, so is 𝐴1 𝐴2 (closure under ∘)
Proof: …
Theorem: If A is a regular language, so is A* (closure under ∗)
Proof: …
Proof by Contradiction
We use this type of reasoning frequently in everyday life, as in the following
example.
Jack sees Jill, who has just come in from outdoors. On observing that she is
completely dry, he knows that it is not raining.
His “proof” that it is not raining is that if it were raining (the assumption that
the statement is false), Jill would be wet (the obviously false consequence).
Therefore, it must not be raining.
Proof by Induction
Proof by induction is an advanced method used to show that all elements of an infinite
set have a specified property.
For example, we may use a proof by induction to show that an arithmetic expression
computes a desired quantity for every assignment to its variables, or that a program
works correctly at all steps or for all inputs.
Proof by Induction
The format for writing down a proof by induction is as follows.
Basis: Prove that P(1) is true.
Induction Hypothesis: Assume that P(i) is true for each i ≥ 1.
Induction Step: Use this assumption to show that P(i + 1) is true.
Proof by Induction
The idea behind inductive proofs is this: imagine there is an infinite staircase, and you want to know whether or not you
can climb and reach every step.
Proof by Induction
Closure Properties for Regular Languages
Theorem: The class of regular languages is closed under the union operation.
In other words, if A1 and A2 are regular languages, so is A1 ∪ A2.
Proof: Let 𝑀1 = (𝑄1 , Σ, 𝛿1 , 𝑞1 , 𝐹1 ) recognize 𝐴1
𝑀2 = (𝑄2 , Σ, 𝛿2 , 𝑞2 , 𝐹2 ) recognize 𝐴2
Construct 𝑀 = (𝑄 , Σ, 𝛿 , 𝑞0, 𝐹 ) recognizing 𝐴1 ∪ 𝐴2
𝑀 should accept input 𝑤 if either 𝑀1 or 𝑀2 accept 𝑤.
Closure Properties for Regular Languages
Theorem: If 𝐴1 , 𝐴2 are regular languages, so is 𝐴1 ∪ 𝐴2 (closure under ∪)
Components of 𝑴:
𝑀1 𝑄 = 𝑄1 × 𝑄2
𝑞 𝑀 = 𝑟1 , 𝑟2 𝑟1 ∈ 𝑄1 and 𝑟2 ∈ 𝑄2 }
𝑞0 = (𝑞1 , 𝑞2 )
𝑀2 ?𝑞, 𝑟 𝛿 𝑟1 , 𝑟2 , 𝑎 = 𝛿1 𝑟1 , 𝑎 , 𝛿2 𝑟2 , 𝑎
𝐹 = 𝐹1 × 𝐹2 NO!
𝐹 = 𝐹1 × 𝑄2 ∪ 𝑄1 × 𝐹2
[gives intersection]
𝑟
( F = {(r1 , r2)| r1 ∈ F1 or r2 ∈ F2} )
Closure Properties for Regular Languages
Theorem: If 𝐴1 , 𝐴2 are regular languages, so is 𝐴1 𝐴2 (closure under ∘)
Proof: Let 𝑀1 = (𝑄1 , Σ, 𝛿1 , 𝑞1 , 𝐹1 ) recognize 𝐴1
𝑀2 = (𝑄2 , Σ, 𝛿2 , 𝑞2 , 𝐹2 ) recognize 𝐴2
Construct 𝑀 = (𝑄 , Σ , 𝛿 , 𝑞0, 𝐹 ) recognizing 𝐴1 𝐴2
𝑀1 𝑀2
𝑀 should accept input 𝑤
if 𝑤 = 𝑥𝑦 where
𝑀
𝑀1 accepts 𝑥 and 𝑀2 accepts 𝑦.
𝑤
𝑥 𝑦
Doesn’t work: Where to split 𝑤?
