Regular Languages

Properties of Regular Languages

Standard Representations of Regular Languages

A language L over an alphabet S is regular

iff

• It is accepted by FA (DFA, NFA, or NFA-^e).

• It is described by a regular expression.

• It is generated by regular grammar (Left-linear or Right-linear).

Standard Representations of Regular Languages

Regular Languages

Regular

Expressions

Regular Grammars (Left/Right Linear) FA

(DFA/NFA/NFA- e)

When we say: We are given a Regular Language

We mean:

L

Language is in a standard Representation (FA/RE/RG)

L

Standard Representations of Regular Languages

Closure Properties

• Recall a closure property is a statement that a certain operation on languages, when applied to languages in a class, produces a result that is also in that class.

• For regular languages, we can use any of its representations to prove a closure property.

Given two regular languages L

and L

, is their union is also regular ? If it is true for all regular

languages, then family of regular

languages is closed under union.

L 1 L ₂

Are regular Languages For regular languages and

we will prove that:

Properties of RLs

We say: The family of Regular languages are

closed under

L 1 Regular language

( ) ^M ₁ ^L ₁

L = M 1

Single final state

NFA M 2

L 2

Single final state

( ) ^M ₂ ^L ₂

L =

Regular language

NFA

Example

a

b

M 1

{ } ^ba

L ₂ = ^{b a}

M 2

L

={a

b :n≥0}

Union

NFA for

M 1

M 2

!

∪ !

l l l

l

Example

a

b

b a

l l l

l

}

1 { a b L = ⁿ

}

2 { ba L =

} {

}

2 {

1 L a b ba

L È = ⁿ È

NFA for

Concatenation

NFA for L 1 L 2

M 1 M ₂

l l

Example

NFA for

a

b _b a

}

1 { a b L = ⁿ

}

2 { ba L =

} {

} }{

2 {

1 L a b ba a bba

L = ⁿ = ⁿ

l l

³ 0

n

Star Operation

NFA for L ₁ *

M 1

l

l

1 * Î L

l

l l

Example

The string in L

* is w NFA for

* } {

1 * a b L = ⁿ

a

b

}

1 { a b L = ⁿ l

l

l

l

1 2 1

L w

w w

w w

i

k

Î

= !

Reversal

L ₁ R

M 1

NFA for 1 ¢ M

1. Reverse all transitions

2. Mark initial state as final state and vice versa

L 1

Example

}

1 { a b L = ⁿ

a

b

M 1

}

1 R { ba n

L =

a

b

1 ¢

M

Complement

1. Take the DFA that accepts L 1

M 1

L 1 ¢

M 1

L 1

2. Make final states non-final,

and vice-versa

Example

}

1 { a b L = ⁿ

a

b

M 1

b a,

b a,

} {

* } ,

1 { a b a b

L = - ⁿ a

b

1 ¢ M

b a,

b

a,

Intersection

DeMorgan’s Law: L 1 Ç L 2 = L 1 È L 2

2 1

, L

L regular

2 1

, L

L regular

2

1

L

L È regular

2

1

L

L È regular

2

1

L

L Ç regular

Example

}

1 { a b L = ⁿ

} ,

2 { ab ba L =

regular regular

}

2 {

1 L ab

L Ç =

regular

Example

a _b

b a

b a,

b

} a,

2 {

1 L ab

L Ç =

Intersection (Product)

L₁ = L(M₁), M₁ = (Q, ^S, ^d1, q0, F₁), ^{Q = {}q0, q1…... q_m,^} L₂ = L(M₂), M₂ = (P, ^S, ^d₂, p₀, F₂), Q = {p₀, p₁…... p_n,} M₁ and M₂ are DFAs.

Define new automation, M’ = (Q’, ^S, ^d’, (q₀, p₀), F’) Q’ = QXP = {(qi, p_j): qi Q, p_j P}

Define transition function ^{d’ s.t.}

d’( (q_i, p_j), a ) = (q_k, p_l) If ^d₁(q_i, a ) = q_k

AND d₂(p_j, a ^{) =} p_l

Define transition for all states.

The initial state is (q₀, p₀),

F’ is the set of all states s.t. (q_i, p_j) s.t.

qi, F₁, p_j F₂

Example-1

Example-2

Find product

DIFFERENCE

L₁ = L(M₁), M₁ = (Q, ^S, ^d₁, q₀, F₁), Q = {q₀, q₁…... q_m,} L₂ = L(M₂), M₂ = (P, ^S, ^d₂, p₀, F₂), Q = {p₀, p₁…... p_n,} M₁ and M₂ are DFAs

!

− !

= !

∩ !

2 1

, L

L regular

regular regular

!

, !

!

∩ !

DIFFERENCE

If L₁ and L₂ are regular languages, then So is L₁ - L₂ L₁ - L₂ consists of strings in L₁ but not L₂ i.e.

!

− !

= !

∩ !

Let M₁ and M₂ be DFA’s whose languages are L₁ and L₂, respectively.

Construct C, the product automaton of M₁ and M₂. Make the final states of C be the pairs where M₁-state is final but M₂-state is not.

Example

Exercise

L

= L ( (a+b)a*) L

= L( baa*)

For given languages L

and L

, construct the FAs.

• Union

• Star closure

• Concatenation

• Complement

• Reversal

• Intersection

• Difference

Exercise

L₁ = L ( (a+b)a*) L₂ = L( baa*)

!

⊝ !

= {': ' ∈ !

*+ ' ∈

!

,-. ' /0 1*. /1 ,*.ℎ !

314 !

} 1*+ (!

, !

) = {': ' ∉ !

314 ' ∉ !

}

:*+ (!

, !

) = {' ∶ ' ∈ !

*+ ' ∈ !

}

! = {-<: - ∈ !, < ∈ !

}

Exercise

L₁ = {w ε {0, 1 }* : w consists of 0’s in multiple of 3}

L₂ = {w ε {0, 1 }* : w consists of odd number of 0’s}

!

⊝ !

= {': ' ∈ !

*+ ' ∈

!

,-. ' /0 1*. /1 ,*.ℎ !

314 !

} 1*+ (!

, !

) = {': ' ∉ !

314 ' ∉ !

}

:*+ (!

, !

) = {' ∶ ' ∈ !

*+ ' ∈ !

}

! = {-<: - ∈ !, < ∈ !

}

Exercise

L

= {w ε {0, 1 }* : w consists of 0’s in multiple of 3}

L

= {w ε {0, 1 }* : w consists of odd number of 0’s}

For given languages L

and L

, find FA for

• Union

• Star closure

• Concatenation

• Complement

• Reversal

• Intersection

• Difference

Reversal of Regular Expression

Basis: If r is a primitive RE (∅, λ or a ε ∑ ), then r^R= r.

Induction: If r₁ and r₂ are two REs (r₁ + r₂)^R = (r₁)^R + (r₂)^R

(r₁r₂)^R = (r₂)^R.(r₁)^R (r₁*)^R = ((r₁)^R)*

Reversal of Regular Expression: Example

Let r₁ = 01* , r₂ =10*.

(r₁ + r₂)^R = (01* + 10*)^R = (01*)^R+ (10*)^R

= (1*)^R0^R + (0*)^R1^R

= (1^R)*0 + (0^R)*1

= 1*0+ 0*1

Homomorphism

A homomorphism on an alphabet is a function that gives a string for each symbol in that alphabet.

h : ∑ Γ*

Where ∑ and Γ are alphabets.

Rules: h(a₁a₂ … a_n-1a_n) = h(a₁)h(a₂) …… h(a_n-1)h(a_n) h(a₁+ a₂) = h(a₁) + h(a₂)

h( (a₁)* ) = (h(a₁))*

Example: h(0) = ab; h(1) = λ

∑ = {0, 1} Γ ={a, b}

h(01010) = h(0)h(1)h(0)h(1)h(0)

= (ab)(λ)(ab)(λ)(ab)(λ)(ab) = ababab

Closure Under Homomorphism

If L is a regular language, and h is a homomorphism on the alphabet of language L.

Then h(L) = {h(w) | w εL} is also a regular language.

Proof: Let r be a regular expression for L.

Apply h to each symbol in r to form a new RE r’

The new RE r’ generates language h(L).

Closure Under Homomorphism : Example

Let h(0) =ab; h(1) = λ.

∑ = {0, 1} Γ ={a, b}

If L is the RL with regular expression 01* + 10*.

Then, h(L) is the homomorphism on the alphabet of language L.

The regular expression of language h(L) is r’ = h(01* +10*)

= h(0)(h(1))* + h(1) (h(0)*

= (ab)(λ)* + (λ)(ab)*

= (ab)λ + λ (ab)*

= (ab) + (ab)*

= (ab)*

Closure Under Homomorphism : Example

Let h(a) =dbcc; h(b) = bdc.

∑ = {a, b} Γ ={b, c, d}

If L is the regular language denoted by RE r = (a + b*) (aa*).

Show that h(L) is also regular language.

Right Quotient of Languages

Let L

and L

be languages on the same alphabet.

Then the right quotient of L

with L

is

L

/ L

= {x: xy L

for some y L

}

In other words, if the string in L

has a

suffix from L

, remove the suffix and the

resulting string is in L

/L

Right Quotient of Languages: Example

L₁ = {aⁿb^m : n ≥ 1, m ≥ 0} ∪ {ba}

L₁ = {ba, a, aa, aaa, …. ab, abb, …… aab, aabb……}

L₂ = {b^m : m ≥ 1}

L₂ = {b, bb, bbb, ….. }

Then the right quotient of L₁ with L₂ is L₁ / L₂ = {aⁿb^m : n ≥ 1, m ≥ 0}

Closure under right quotient

If L

, L

are regular then L

/L

is regular.

L

is regular so it has a FA.

For each node in the FA of L

, check if there is a walk from that node to a final node using a string in L

.

If so, mark that node final.

So L

/L

is regular.

Example

L

= L(a*baa*); L

= L(ab*) DFA for L

:

q₀ q1 q2

q3

a

b a

a

a, b

b b

Example

L

= L(a*baa*); L

= L(ab*) DFA for L

:

L

= {a, ab, abb … }

p0 p1

p2

b a

a

a, b

b

Example

L

= L(a*baa*); L

= L(ab*)

Remove final marking, remember final state is q2.

q₀ q1 q2

q3

a

b a a

a, b b b

L

= {a, ab, abb … }

Example

L

= L(a*baa*); L

= L(ab*)

For each node, look for a walk on element of L₂ to q₂.

q₀ q1 q2

q3

a

b a a

a, b b b

L

= {a, ab, abb … }

Example

L

= L(a*baa*); L

= L(ab*) DFA for L

/L

:

q0 q1 q2

q3

a

b a a

a,b

b b

Find Right Quotient

L

= {a

b

: n ≥1, m ≥0} ∪ {ba}

L

= {b

: m ≥ 1 }

L

/L

= ?

Exercise

L

=L(a*baa*) L

=L(aba*)

• Find L

/L

• If head of a language is defined as head(L) = {x : xy L for some y

∑*}

Find head(L

) and head(L

)

Elementary Questions about

Regular Languages

Membership Question

Question: Given regular language and string

how can we check if ?

L

L w Î

w

Answer: Take the DFA that accepts and check if is accepted

L

w

DFA

L w Î

DFA

L w Ï w

w

If there is a path from initial state to final state with labeled w; Accepted

If there is no path from initial state to final state with labeled w; Rejected

Given regular language how can we check

if is empty: ?

L L

Take the DFA that accepts

Check if there is any path from the initial state to a final state

L )

( L = Æ

Question:

Answer:

DFA

Æ

¹ L

DFA

Æ

=

L

Given regular language how can we check

if is finite?

L L

Take the DFA that accepts

Check if there is a walk with cycle from the initial state to a final state

L

Question:

Answer:

DFA

L is infinite

DFA

L ^{is finite}

Given regular languages and

how can we check if ? L 1 L ₂

2

1 L

L =

Question:

Æ

= Ç

È

Ç ) ( ) ( L ₁ L ₂ L ₁ L ₂

Find if

Answer:

Æ

= Ç

È

Ç ) ( ) ( L ₁ L ₂ L ₁ L ₂

Æ

= Ç ₂

1 L

L ^and L ₁ Ç L ₂ = Æ

2

1 L

L = L 1

L 2 L ₂ L ₁

2

1 L

L Í L ₂ Í L ₁

L 2 L ₁

Æ

¹ Ç

È

Ç ) ( ) ( L ₁ L ₂ L ₁ L ₂

Æ

¹ Ç ₂

1 L

L ^or L ₁ Ç L ₂ ¹ Æ L 1

L 2 L ₂ L ₁

2

1 L

L Ë L ₂ Ë L ₁

2

1 L

L ¹

Non-regular languages

Regular Languages

Every finite language is regular.

Some infinite languages are regular L

={a

b : n >=0}

Regularity:

The language is regular if, in processing any string, the information that has to be

remembered at any stage is strictly limited.

Some infinite languages are not regular

L

= {a

b

: n >=0}

How can we prove that a language L is regular?

Prove that there is DFA M that accepts L

Prove that there is RE r that generates L

Prove that there is RG G that generates L

Regular languages

b

a * b * c + a

...

etc

* ) ( a b c

b + +

Non-regular languages { a ⁿ b ⁿ : n ³ 0 }

}*}

, { :

{ vv ^R v Î a b

How can we prove that a language is not regular?

L

Prove that there is no DFA that accepts L

Problem: this is not easy to prove

Solution: the Pumping Lemma !!!

The pumping Lemma uses pigeonhole principle.

The Pigeonhole Principle

pigeons

pigeonholes

4

3

A pigeonhole must

contain at least two pigeons

...

...

pigeons

pigeonholes

n

m ^{n > m}

The Pigeonhole Principle

...

pigeons

pigeonholes

n m

m

n > There is a pigeonhole

with at least 2 pigeons

The Pigeonhole Principle

If we put n objects into m boxes and if n > m

• then at least one box must have more than

one object in it.

The Pigeonhole Principle and

DFAs

DFA with 4 states

q 1 a q ₂ q ₃ b

q 4

b

b b

b

a a

aab

q 1 a q ₂ q ₃ b

q 4

b

b

b

a a

a

In walks of strings: no state

is repeated

abab aabb aabbb abbabb

In walks of strings:

q 1 a q ₂ q ₃ b

q 4

b

b

b

a a

a

a state

is repeated

If string has length :

q 1 a q ₂ q ₃ b

q 4

b

b

b

a a

a

w ^{| w | ³ 4}

Thus, a state must be repeated Then the transitions of string

are more than the states of the DFA

w

In general, for any DFA:

String has length number of states w ³

A state must be repeated in the walk of q w

... q ...

walk of w

Repeated state

In other words for a string : transitions are pigeons states are pigeonholes

q a

w

... q ...

walk of w

Repeated state

The Pumping Lemma

Take an infinite regular language L

There exists a DFA that accepts L

states m

Take string with w w Î L

There is a walk with label : w

...

walk w

If string has length w ^{| w | ³ m}

of states of DFA)

then, from the pigeonhole principle:

a state is repeated in the walk w

... q ...

walk w

q

... q ...

walk w

Let be the first state repeated in the

walk of w

Write w = x y z

... q ...

x

y

z

... q ...

x

y

z

Observations: length | x y | £ m number of states of DFA

1

|

| y ³

length

The string is accepted.

z

Observation: x

... q ...

x

y

z

The string x y z

is accepted Observation:

... q ...

x

y

z

The string is accepted

z y y

Observation: x

... q ...

x

y

z

The string is accepted

z y y y

Observation: x

... q ...

x

y

z

The string is accepted

z y

x ⁱ

In General:

...

, 2 , 1 ,

= 0 i

... q ...

x

y

z

L z

y x ⁱ

In General: i = 0 , 1 , 2 , ...

... q ...

x

y

z

Language accepted by the DFA

In other words, we described:

The Pumping Lemma !!!

The Pumping Lemma:

• Given a infinite regular language L

• there exists an integer for any string m

with length

L

w Î ^{| w | ³ m}

Then, we we can decompose w = x y z

with and | x y | £ m | y | ³ 1

such that: x y ⁱ z Î L i = 0 , 1 , 2 , ...

Applications of

the Pumping Lemma

Theorem: The language L = { a ⁿ b ⁿ : n ³ 0 }

is not regular

Proof: Use the Pumping Lemma

Assume for contradiction

that is a regular language L

Since is infinite.

we can apply the Pumping Lemma

L

} 0 :

{ ³

= a b n

L ^{n n}

Let be the integer in the Pumping Lemma

Pick a string such that: w _{w Î L}

m w | ³

length |

m m b a

w =

We pick

m

} 0 :

{ ³

= a b n

L ^{n n}

it must be that length

From the Pumping Lemma

1

|

| ,

|

| x y £ m y ³

b ab

aa aa

a b

a

xyz = ^{m m} = ... ... ... ...

1

, ³

= a k

y ^k

x y ^z

m m

Write: a ^m b ^m = x y z

Thus:

From the Pumping Lemma: x y ⁱ z Î L ...

, 2 , 1 ,

= 0 i

Thus:

m m b a

z y

x =

L z

y

x ² Î

1

, ³

= a k

y ^k

From the Pumping Lemma:

L b

ab aa

aa aa

a z

xy ² = ... ... ... ... ... Î

x y ^z

k

m + m

Thus:

L z

y

x ² Î

m m b a

z y

x = y = a ^k , k ³ 1

y

L b

a ^{m + k m} Î

L b

a ^{m + k m} Î

} 0 :

{ ³

= a b n L ^{n n}

BUT:

L b

a ^{m + k m} Ï

CONTRADICTION!!!

1

≥

k

Our assumption that

is a regular language is not true

L

Conclusion: L is not a regular language

Therefore:

More Applications of

the Pumping Lemma

Theorem: The language is not regular

Proof: Use the Pumping Lemma

*}

:

{ Î S

= vv v

L ^{R S = { a , b }}

Assume for contradiction

that is a regular language L

Since is infinite

we can apply the Pumping Lemma

L

*}

:

{ Î S

= vv v

L ^R

m m

m

m b b a a

w =

We pick

Let be the integer in the Pumping Lemma

Pick a string such that: w _{w Î L}

m w | ³

length | m

and

*}

:

{ Î S

= vv v

L ^R

Write a ^m b ^m b ^m a ^m = x y z

it must be that length

From the Pumping Lemma

a ba

bb ab

a aa

a

xyz = ... ... ... ... ... ...

x y _z

m m m m

1

|

| ,

|

| x y £ m y ³

1

, ³

= a k

y ^k

Thus:

From the Pumping Lemma: x y ⁱ z Î L ...

, 2 , 1 ,

= 0 i

Thus: x y ² z Î L

1

, ³

= a k

y ^k

m m

m

m b b a a

z y

x =

From the Pumping Lemma:

L a

ba bb

ab a

aa aa

a z

xy ² = ... ... ... ... ... ... ...

x y _z

k

m + m m m

1

, ³

= a k

y ^k

y

L z

y

x ² Î

Thus:

m m

m

m b b a a

z y

x =

L a

b b

a ^{m + k m m m} Î

L a

b b

a ^{m + k m m m} Î

L a

b b

a ^{m + k m m m} Ï

BUT:

CONTRADICTION!!!

³ 1 k

*}

:

{ Î S

= vv v

L ^R

Our assumption that

is a regular language is not true

L

Conclusion: L is not a regular language

Therefore:

Regular languages Non-regular languages

} 0 ,

:

{ ³

= a b c ⁺ n l

L ^{n l n l}

Theorem: The language is not regular

Proof: Use the Pumping Lemma

} 0 ,

:

{ ³

= a b c ⁺ n l

L ^{n l n l}

Assume for contradiction

that is a regular language L

Since is infinite

we can apply the Pumping Lemma

L

} 0 ,

:

{ ³

= a b c ⁺ n l

L ^{n l n l}

m m

m b c a

w = ²

We pick

Let be the integer in the Pumping Lemma

Pick a string such that: w _{w Î L}

m w | ³

length | m

} 0 ,

:

{ ³

= a b c ⁺ n l L ^{n l n l}

and

Write a ^m b ^m c ^{2 m} = x y z

it must be that length

From the Pumping Lemma

c cc

bc ab

aa aa

a

xyz = ... ... ... ... ... ...

x y _z

m m 2 m

1

|

| ,

|

| x y £ m y ³

1

, ³

= a k

y ^k

Thus:

From the Pumping Lemma: x y ⁱ z Î L ...

, 2 , 1 ,

= 0 i

Thus:

m m

m b c a

z y

x = ²

L xz

z y

x ⁰ =

1

, ³

= a k

y ^k

From the Pumping Lemma:

L c

cc bc

ab aa

a

xz = ... ... ... ... ... Î

x _z

k

m - m 2 m

m m

m b c a

z y

x = ² y = a ^k , k ³ 1 L

xz Î

Thus: a ^{m - k} b ^m c ^{2 m} Î L

L c

b

a ^{m - k m 2 m} Î

L c

b

a ^{m - k m 2 m} Ï

BUT:

CONTRADICTION!!!

} 0 ,

:

{ ³

= a b c ⁺ n l L ^{n l n l}

³ 1

k

Our assumption that

is a regular language is not true

L

Conclusion: L is not a regular language

Therefore:

Regular languages

Non-regular languages L = { a ^{n !} : n ³ 0 }

Theorem: The language

is not regular

Proof: Use the Pumping Lemma

} 0 :

{ ^! ³

= a n

L ⁿ

n n

n ! = 1 × 2 ! ( - 1 ) ×

Assume for contradiction

that is a regular language L

Since is infinite

we can apply the Pumping Lemma

L

} 0 :

{ ^! ³

= a n

L ⁿ

!

a m

w =

We pick

Let be the integer in the Pumping Lemma

Pick a string such that: w _{w Î L}

m w | ³

length | m

} 0 :

{ ^! ³

= a n

L ⁿ

Write a ^{m !} = x y z

it must be that length

From the Pumping Lemma

a aa

aa aa

aa a

a

xyz = ^{m !} = ... ... ... ... ...

x y _z

m m ! - m

1

|

| ,

|

| x y £ m y ³

m k

a

y = ^k , 1 £ £

Thus:

From the Pumping Lemma: x y ⁱ z Î L ...

, 2 , 1 ,

= 0 i

Thus:

!

a m

z y

x =

L z

y

x ² Î

m k

a

y = ^k , 1 £ £

From the Pumping Lemma:

L a

aa aa

aa aa

aa a

z

xy ² = ... ... ... ... ... ... Î

x y _z

k

m + m ! - m

Thus:

!

a m

z y

x = y = a ^k , 1 £ k £ m L

z y

x ² Î

y

L

a ^{m ! + k} Î

L a ^{m ! + k} Î

!

! k p

m + =

} 0 :

{ ^! ³

= a n

L ⁿ

Since:

m k £

£ 1

There must exist such that: p

However:

)!

1 (

) 1 (

!

!

!

!

!

!

+

=

+

=

+

<

+

£

+

£

m

m m

m m

m

m m

m k m

m ! + _for m > 1

)!

1 (

! + k < m + m

!

! k p

m + ¹ ^{for any} p

L a ^{m ! + k} Î

L a ^{m ! + k} Ï

BUT:

CONTRADICTION!!!

} 0 :

{ ^! ³

= a n

L ⁿ

m k £

£

1

Our assumption that

is a regular language is not true

L

Conclusion: L is not a regular language

Therefore:

Exercise

Prove that the following languages are not regular.

• L ={a

b

a

: k ≥ n+l }

• L ={a

b

: n ≥ 0 } ∪ {a

b

: n ≥ 0 } ∪ {a

b

: n ≥ 0 }

• L ={a

: n ≥ 1 }

Are the following languages are regular ?

• L ={w ε {a, b, c}* : |w| = 3n

(w)}

• L ={w

cw

: w

, w

ε {a, b}*, w

≠w

}

Exercise

Let ^{L = {a}

^b

: n ≥ 100, m ≤ 50}

• Can you use the pumping lemma to show that L is regular ?

• Can you use the pumping lemma to show

that L is regular ?

Lex

Lex: a lexical analyzer

• A Lex program recognizes strings

• For each kind of string found

the lex program takes an action

Var = 12 + 9;

if (test > 20) temp = 0;

else

while (a < 20) temp++;

Lex

program

Identifier: Var Operand: = Integer: 12 Operand: + Integer: 9

Semicolumn: ; Keyword: if

Parenthesis: ( Identifier: test ....

Input

Output

In Lex strings are described with regular expressions

“if”

“then”

“+”

“-”

“=“

/* operators */

/* keywords */

Lex program

Regular expressions

(0|1|2|3|4|5|6|7|8|9)+ /* integers */

/* identifiers */

Regular expressions

(a|b|..|z|A|B|...|Z)+

Lex program

integers

[0-9]+

(0|1|2|3|4|5|6|7|8|9)+

(a|b|..|z|A|B|...|Z)+ [a-zA-Z]+

identifiers

Each regular expression

has an associated action (in C code)

Examples:

\n

Regular expression Action

linenum++;

[a-zA-Z]+ printf(“identifier”);

[0-9]+ prinf(“integer”);

Default action: ECHO;

Prints the string identified

to the output

A small lex program

%%

[a-zA-Z]+ printf(“Identifier\n”);

[0-9]+ printf(“Integer\n”);

[ \t\n] ; /*skip spaces*/

1234 test

var 566 78 9800

Input Output

Integer

Identifier

Identifier

Integer

Integer

Integer

%%

[a-zA-Z]+ printf(“Identifier\n”);

[0-9]+ prinf(“Integer\n”);

[ \t] ; /*skip spaces*/

. printf(“Error in line: %d\n”, linenum);

Another program

%{

int linenum = 1;

%}

\n linenum++;

1234 test

var 566 78 9800 +

temp

Input Output

Integer Identifier Identifier Integer Integer Integer

Error in line: 3

Identifier

Lex matches the longest input string

“if”

“ifend”

Regular Expressions

Input: ifend if Matches: “ifend” “if”

Example:

Internal Structure of Lex

Lex

Regular

expressions NFA DFA Minimal DFA

The final states of the DFA are

associated with actions

Thank You