Language Recognition (12.

4)
Longin Jan Latecki
Temple University

Based on slides by Costas Busch from the course

http://www.cs.rpi.edu/courses/spring05/modcomp/
and …

1
 Three Equivalent Representations
Regular
expressions

Each
can
describe
the others Regular
Finite
languages
automata

Kleene’s Theorem:
For every regular expression, there is a deterministic
finite-state automaton that defines the same
language, and vice versa.

2
 EXAMPLE 1

Consider the language { ambn | m, n  N},

which is represented by the regular
expression a*b*.

A regular grammar for this language can

be written as follows:

S  | aS | B
B  b | bB.

3
Regular Regular Grammar
Expression
a* S   | aS
(a+b)* S   | aS | bS
a* + b* S|A|B
A  a | aA
B  b | bB
a*b S  b | aS
ba* S  bA
A   | aA
(ab)* S   | abS
4
 NFAs  Regular grammars
Thus, the language recognized by FSA
is a regular language
Every NFA can be converted into a corresponding regular
grammar and vice versa.
Each symbol A of the grammar is associated with a non-
terminal node of the NFA sA, in particular, start symbol
S is associated with the start state sS.
Every transition is associated with a grammar production:
T(sA,a) = sB  A  aB.
Every production B   is associated with final state sB.

5
Equivalent FSA and regular grammar, Ex. 4, p. 772.

G=(V,T,S,P)
V={S, A, B, 0, 1} with
S=s0, A=s1, and B=s2,
T={0,1}, and productions are
S  0A | 1B | 1 | λ
A  0A | 1B | 1
B  0A | 1B | 1 | λ

6
 Kleene’s Theorem

Languages
Generated by
Regular Expressions
 Languages
Recognized
by FSA

7
 We will show:

Languages
Generated by  Languages
Recognized
Regular Expressions by FSA

Languages
Generated by  Languages
Recognized
Regular Expressions by FSA

8
 Proof - Part 1

Languages
Generated by  Languages
Recognized
Regular Expressions by FSA

For any regular expression r

the language L(r ) is recognized
by FSA (= is a regular language)
Proof by induction on the size of r
9
 Induction Basis
Primitive Regular Expressions: ,  , a
NFAs

L( M1 )  L( )

regular
L( M 2 ) {} L( )
languages
a
L( M 3 ) {a} L(a )

10
 Inductive Hypothesis

Assume
for regular expressions r1 andr2
that
L(r1 ) and L(r2 ) are regular languages

11
 Inductive Step
We will prove:
Lr1  r2 

Lr1 r2 
Are regular
Languages
Lr1 *

Lr1 
12
By definition of regular expressions:

Lr1  r2  Lr1  Lr2 

Lr1 r2  Lr1  Lr2 

Lr1 * Lr1 *

Lr1  Lr1 
13
By inductive hypothesis we know:
L(r1 )and L(r2 ) are regular languages
We need to show:
Regular languages are closed under:
Union Lr1  Lr2 
Concatenation Lr1  Lr2 
Star Lr1 *
This fact is illustrated in Fig. 2 on p. 769.

14
Therefore:
Lr1  r2  Lr1  Lr2 

Are regular
Lr1 r2  Lr1  Lr2 
languages

Lr1 * Lr1 *

And trivially: L((r1 )) is a regular language

15
 Proof - Part 2

Languages
Generated by  Languages
Recognized
Regular Expressions by FSA

For any regular languageL there is

a regular expression r with L( r ) L

Proof by construction of regular expression

16
Since L is regular take the
NFA M that accepts it

L ( M ) L

Single final state

17
From M construct the equivalent
Generalized Transition Graph
in which transition labels are regular
expressions

Example:
M
a c a c
a, b a b
18
 b b
Another Example:
a
q0 q1 a, b q2
b

b b
a
q0 q1 a  b q2
b
19
 b b
Reducing the states:
a
q0 q1 a  b q2
b

bb * a b

q0 bb * (a  b) q2
20
Resulting Regular Expression:

bb * a b

q0 bb * (a  b) q2

r (bb * a ) * bb * (a  b)b *

L ( r ) L ( M ) L
21
 In General
Removing states: e
d c
qi q qj
a b

ae * d ce * b
ce * d
qi qj
ae * b
22
The final transition graph:
r1 r4
r3
q0 qf
r2

The resulting regular expression:

r r1 * r2 (r4  r3r1 * r2 ) *

L ( r ) L ( M ) L
23
Three Equivalent Representations
Regular
expressions

Each
can
describe
the others Regular
Finite
languages
automata

24