Dfa

PRESENTED BY SHRADDHA GUPTA SOPAN SHUKLA 2ND C.S.E.

REGULAR EXPRESSION Regular expression can define exactly the same languages that the various forms of automata describe: the regular languages. Regular expression offer something that automata do not: a declarative way to express the strings, we want to accept. The set of regular expressions is defined by the following rules: Let be a given alphabet. Then 1. , and a are all regular expressions.These are called primitive regular expressions. 2. If r1 and r2 are regular expressions, so are r1+r2, r1.r2 , r1* and (r1). 3. A string is a regular expression if and only if it can be derived from the primitive regular expressions by a finite number applications of the rules in 2.

OPERATORS OF REGULAR EXPRESSION 1. UNION :

L1 U L2

It denotes the set of string that are in either L1 or L2 or both. L1={001,10,111) and L2 ={ ,001} then L1 U L2 = { 2. CONCATENATION:

,10,001,111}.

L1.L2

It is a set of strings that can be formed by taking any string in L1 and concatenating it with any strings in L2. It is denoted by ‘.’. 3. STAR:

L*

It represents a set of those strings that can be formed by taking any number of strings from L, possibly with repetitions and concatenating all of them. Note : L+ represents the positive closure.

EXAMPLE:

L(a*.(a+b))

If r1 and r2 are regular expressions, then 2. L(r1+r2) = L(r1) U L(r2) 3. L(r1.r2) = L(r1).L(r2) 4. L(r1*) = (L(r1))* L(a*.(a+b)) = L(a*).L(a+b) (L(a))*.(L(a) U L(b)) { ,a,aa,aaa, …}{a,b} {a,aa,aaa,…,b,ab,aab,…}

r1 = (a+b)*(a+bb) L(r1) = {a,bb,aa,abb,ba,bbb,…} L(r1) is the set of all strings on {a,b}, terminated by either an a or a bb.

CONSTRUCTION OF FA FOR REGULAR EXPRESSIONS

Regular Expression

Regular Set

Finite Automata

{} { } a

{a}

(r1+r2)

R1 U R2

(r1.r2)

R1R2

r*

R1

a

Regular language

L( M1 ) = L1 NFA

M1

Single accepting state

L1

Regular language

L( M 2 ) = L2 NFA

M2

Single accepting state

L2

Example n≥0

n

L1 = {a b}

a

M1 b

M2 L2 = { ba}

b

a

Union

• NFA for

L1 ∪ L2

M1

λ λ

M2

Example NFA for

n

L1 ∪ L2 = {a b} ∪ {ba} n

L1 = {a b}

•

a

λ λ

b

L2 = {ba} b

a

Concatenation • NFA for

L1L2 M1

M2 λ

λ

• • NFA for

Example n

n

L1L2 = {a b}{ba} = {a bba} n

L1 = {a b}

L2 = {ba}

a b

λ

b

a

λ

Star Operation • NFA for L1 *

λ

λ ∈ L1 *

M1 λ

λ

λ

Example • NFA for

w = w1w2  wk

n

L1* = {a b} *

wi ∈ L1

λ n

L1 = {a b}

a

λ

λ

b

λ

ALGEBRAIC LAWS • Associativity and Commutativity (P+Q)+R = P+(Q+R) P+Q = Q+P • Identity Law +L =L+ =L L = L =L • Distributed Law x * (y+z) = x*y + x*z • Idempotent Law L+L = L; L*L = L

Union Example EX: Draw the DFA forx has even length or L = { x ∈ {0,1}* | ends with 11 } The solution involved making a table of states with rows keeping track of parity, and columns keeping track of the progress towards achieving the 11 pattern:

Union Example suffix length

ε

0 mod 2

1 1

0 0 0 0

1 1

1 mod 2

11

0 0

1

1 1

Union Example We could have arrived at this result methodically by noticing that L is the union of two easier languages: L = L1 ∪ L2 L1 = { x ∈ {0,1}* | x has even length} L2 = { x ∈ {0,1}* | x ends with 11 }

Union Example --L1 L1 = { x ∈ {0,1}* | x has even length}

0,1 0,1

Union Example –L2 L2 = { x ∈ {0,1}* | x ends with 11 } 1 1

0 0

1 0

Union Example –L1∪L2 Which together form the union, using the Cartesian Product Construction: 1

0 0 0 0

1 1

0 0

1

1 1

Union Example Upshot: To tell if string is in union, just kept track of active states in both automata. At end, string is in union if it is accepted by at least one automaton. It would be nice if could keep track of both sets of states in a single 1 automaton. 1 0

0,1 0,1

0

1 0

Union Example Assign labels to the states in the two machines 1 a 0,1 0,1 b

x 0

0

1.

1

y 1 0

z

Union Example Keep track of states of both machines by using spliced states. 1 a 0,1 0,1 b

x 0

0

2.

1

y 1 0

z

Union Example

Current spliced state: (a,x)

1 0

a

x

y 1

0

0,1 0,1

1

0

b

1

1

1

0

1

0

1

z

Union Example

Current spliced state: (b,y)

1 0

a

x

y 1

0

0,1 0,1

1

0

b

1

1

1

0

1

0

1

z

Union Example

Current spliced state: (a,z)

1 0

a

x

y 1

0

0,1 0,1

1

0

b

1

1

1

0

1

0

1

z

Union Example

Current spliced state: (b,z)

1 0

a

x

y 1

0

0,1 0,1

1

0

b

1

1

1

0

1

0

1

z

Union Example

Current spliced state: (a,x)

1 0

a

x

y 1

0

0,1 0,1

1

0

b

1

1

1

0

1

0

1

z

Union Example

Current spliced state: (b,y)

1 0

a

x

y 1

0

0,1 0,1

1

0

b

1

1

1

0

1

0

1

z

Union Example

Current spliced state: (a,z)

1 0

a

x

y 1

0

0,1 0,1

1

0

b

1

1

1

0

1

0

1

z

Union Example

Current spliced state: (b,y)

Rejected! 0,1 0,1

x

0

a

y 1

0

0

b

Rejected! 1 1 1

1

0

1

0

1

1 z

Union Example

Q: What splice states should be accepting states? 1

0,1 0,1 b

x 0

0

a

1

y 1 0

z

Union Example –Accept States

A: Any splices that included at least one accept state. F = {(a,x),(a,y),(a,z),(b,z)} 1

0,1 0,1 b

x 0

0

a

1

y 1 0

z

Back to our Example1 0,1 0,1

0

a

x

1

y

z

1

0

0

b (a,x)

Unioner Construction: 0

(a,y)

0

1

0 0

(b,x)

1

(b,y)

0 0

1 (a,z) 1

1 1 (b,z)

MISCELLANEOUS EXAMPLE

Q. Construct a finite automata equivalent to the regular expression. (0+1)*(00+11)(0+1)* Answer: (0+1)*(00+11)(0+1)* q0

q1

• First we draw the state transition as above: • Then in step 2 we eliminate the concatenations by introducing new vertices q2 and q3. • Inter-mediate vertices is shown :

(0+1)* (00+11) q0

q2

q3

(0+1)*

q1

• Now we eliminate * operation by introducing two new vertices q5 and q6 and different moves are shown. (0+1) q3

q5 (00+11) q0

q2

(0+1)

q1 q6

• Now we eliminate concatenations and + (where concatenation is by different states and + i.e.0+1 by (0,1).) 0,1

q0

q5

q7

0

0

q2

0,1

q3 1

q8

1

q6

q1

• After reducing the above operated constructions we get FA equivalent to (0+1)*(00+11)(0+1)*. • Here we are using rules: • For reductions.. 1.Find all edges starting from V2. • 2.Duplicate all edges starting from V1without changing the edge labels. • 3.If V1 is initial state make V2 also initial state and if V2 final state make V1 also final state.

• Above is construction of FA equivalent to (0+1)*(00+11)(0+1)*. • After making the transition and successor table we get the required DFA.

• This is the required DFA. 1

[q0,q9]

0

[q0,q9,q1]

0 0

[q0] 1

1

[q0,q10]

0 1

1

0

[q0,q10,q1]

Conclusion We can now say that regular expressions are very useful for representing certain sets of strings in an algebraic fashion. Actually these describe the languages accepted by finite state automata. And the operations used in the expressions are the only tools for doing that without which it is not possible.

Thank you.