Theory of Computation - Lectures 4 and 5

Formal Definition of Computation
Let M = (Q, ∑ , δ, q0, F) be a finite automaton
and let w = w1w2.....wn be a string where
each wi is a member of the alphabet ∑. Then
M accepts w if a sequence of states r0, r1, ….,rn In
Q exists with three conditions:
1- r0= q0,
2- δ(ri, wi+1)=ri+1, for i=0,...,n-1, and
3- rn∈ F

Cont.






Condition 1 says that the machine starts in
the start state.
Condition 2 says that the machine goes
from state to another according to the
transition function
Condition 3 says that the machine accepts
its input if it ends up in an accept state. We
say that M recognizes language A if

A = {w | M accepts w}

Regular Language


Definition:

A language is called a regular language if
some finite automaton recognizes it.
See example 1.17 p. 41

Designing Finite Automata






Just like artwork, design is a creative
process...
Suppose you are given some language,
and you want to design a FA that
recognizes it...pretend that you are the
machine!
Take symbols, one by one, and and after
each symbol, you should decide whether
the string so far is in the language or not.

Designing Finite Automata –Cont.




What if the string is from earth to moon
long? And your memory (as a FA) is like a
sheet of paper? Worry-less, you will have
to memorize the crucial info only, like:
“What's my status now?”
Example: suppose: alphabet = {0,1}, and
that the language consists of all strings
with an odd number of 1s. You want to
construct a FA E1 to recognize this
language

By pretending that you're the FA, get the
symbols (1 by 1), do you need to
remember all the string? No! Just
remembering the number of 1s so far is
even or not is enough, so that if next is 0,
don't change, if 1, change!


Therefore, you have 2 states, say: q odd, qeven.





Next, assign transitions.
Assign a start state (qeven) in our example,
since no symbol has been entered so far
(0) and 0 is even.



What about Final state (accept)?



See example 1.21 - P.43

Regular Operations


We use them to study properties of regular
languages, those properties will help us
develop a toolbox that will include ways of
proving certain other languages are
nonregular (i.e. beyond the capability of
FA)

Regular Operations


If A and B are languages, then:



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}
The star operation is unary operation (on 1
language) while the union and conc. are
binary operations

Regular Operations – cont.
Let ∑ = {a,b,....,z}, if A = {good, bad}, and B = {boy,
girl} the:

A ∪ B = {good, bad, boy, girl}
A ○ B = {goodboy, goodgirl, badboy, badgirl}
A*= {ε, good, bad, goodgood, badbad, badgood,
goodgoodgood, goodgoodbad, etc.....}

Regular Operations Cont.


Closed under multiplication:

example, if x and y are two numbers from N,
then x*y results a number also from N.




But N is not closed under division,
because x/y may result a number which
isn't member of N, ex. X=1, y=2, x/y=1/2
which isn't member of N
Please read theorems 1.25, 1.26 p.45, 46

Nondeterminism


DFA vs. NFA:

DFA has exactly one exiting transition arrow
for each symbol in the alphabet, NFA
violets that.




DFA uses symbols from alphabet only for
arrow labels, NFA may use others, such as
ε.
What will happen if a state has two arrows
for same input? Or if input is ε?

NFA
0,1
q1

0,1
1

q2

0,ε

q3

1

q
q4
4



Examples:

1.30, 1.33, 1.35 P: 51-53

Formal definition of NFA






Similar to DFA, the NFA has the 5-tuple,
yet the difference is in δ (The Transition
Function)
In DFA, δ takes a state and an input
symbol and produces the next state.
In NFA, δ takes a state and an an input
symbol OR the empty string and produces
the set of possible next states.

Cont.
Therefore, point 3 of the tuple would be as:
δ : Q X ∑ε → P(Q), where
∑ε is the result of ∑ ∪ ε

Example
The formal definition of N1 (slide 13):
1- Q = {q1,q2,q3,q4}
2- ∑ = {0,1}
3- δ is given as:
4- q1 =start state
5- F ={q4}

0

1

ε

q1

{q1}

{q1,q2}

Ф

q2

{q3}

Ф

{q3}

q3

Ф

{q4}

Ф

q4

{q4}

{q4}

Ф

Reading


Every NFA has an equivalent DFA...

To prove, read P.54- P.58


Based on your previous reading (P.45),
read Closure under the regular operations
(P.58-63). Which is similar to, yet easier
than example P.45.

Regular Expressions




In math, we use + and x to build up
expressions like: (5+3)x4 (Gives 32)
Similarly, we use∪ and * to build up

expressions describing languages, called
Regular Expressions (RegEx):
(0 ∪ 1)0* … (Gives a language)

What does (0 ∪ 1)0* mean?


It's a language consisting of all strings starting
with a 0 or 1 followed by any number of 0s.

RegEx – Cont.
(0 ∪ 1)0* is:
- (0 ∪ 1) = ({0}∪{1}) = {0,1}
- 0* means {0}*, means a language consisting of of any
number of 0s.
The concatenation between (0 ∪ 1) and 0* is a
shorthand for for (0 ∪ 1) ○ 0*




Applications of RegEx: many, Grep (text-search)in
Unix and Linux, Perl, C++, text editors etc....
In C++, you can use regex r("(+|-)?[[:digit:]]+");, but
why?

Regex- Example
(0 ∪ 1)* = the language consisting of all possible
strings of 0s and 1s.
If ∑ ={0,1}, then ∑ is a shorthand for (0 ∪ 1).




Generally, if ∑ is any alphabet, the regex ∑
describes the language consisting of all strings of
length 1 over the alphabet, and ∑* describes the
language consisting of all strings over the
alphabet.
∑*1 is the language that contains all strings that
end with 1

Regex- Example-cont.


The language (0∑*) ∪ (∑*1) consists of all

strings that either start with a 0 or end with a 1.
* similar to mathematical precedence ( x before +
for example), in regex, * is done first ,then
concatenation, finally the union. Unless
parentheses are used.

Formal Definition of regex


We say that R is a regex if R:

1. a for some a in the alphabet
2. ε,
3. ᶲ
4. (R1 ∪ R2)
5. (R1 ○ R2)
6. (R1*), where R1 is a regex

Theory of Computation - Lectures 4 and 5

Recommended

More Related Content

What's hot (19)

Viewers also liked (13)

Similar to Theory of Computation - Lectures 4 and 5 (20)

More from Dr. Maamoun Ahmed (7)

Recently uploaded (20)

Theory of Computation - Lectures 4 and 5