Courses

# From Regular Expression to NFA - Thompson’s Construction Personal Learning Notes | EduRev

## Personal Learning : From Regular Expression to NFA - Thompson’s Construction Personal Learning Notes | EduRev

``` Page 1

From Regular Expression to NFA
Thompson’s
Construction
Page 2

From Regular Expression to NFA
Thompson’s
Construction
WVUIT Computer Science
Thompson’s Construction
? Thompson’s construction is a technique
for constructing a NFA from a regular
expression.
? There are a few simple rules that can be
combined to produce a NFA from any
arbitrary regular expression.
Page 3

From Regular Expression to NFA
Thompson’s
Construction
WVUIT Computer Science
Thompson’s Construction
? Thompson’s construction is a technique
for constructing a NFA from a regular
expression.
? There are a few simple rules that can be
combined to produce a NFA from any
arbitrary regular expression.
WVUIT Computer Science
Thompson’s Construction
? For e, construct the NFA:

? For a, construct the NFA:
Page 4

From Regular Expression to NFA
Thompson’s
Construction
WVUIT Computer Science
Thompson’s Construction
? Thompson’s construction is a technique
for constructing a NFA from a regular
expression.
? There are a few simple rules that can be
combined to produce a NFA from any
arbitrary regular expression.
WVUIT Computer Science
Thompson’s Construction
? For e, construct the NFA:

? For a, construct the NFA:
WVUIT Computer Science
Thompson’s Construction
? Suppose N(s) and N(t) are NFAs for regular
expressions s and t, respectively. For the regular
expression s | t, construct the NFA:

Page 5

From Regular Expression to NFA
Thompson’s
Construction
WVUIT Computer Science
Thompson’s Construction
? Thompson’s construction is a technique
for constructing a NFA from a regular
expression.
? There are a few simple rules that can be
combined to produce a NFA from any
arbitrary regular expression.
WVUIT Computer Science
Thompson’s Construction
? For e, construct the NFA:

? For a, construct the NFA:
WVUIT Computer Science
Thompson’s Construction
? Suppose N(s) and N(t) are NFAs for regular
expressions s and t, respectively. For the regular
expression s | t, construct the NFA:

WVUIT Computer Science
Thompson’s Construction
? Suppose N(s) and N(t) are NFAs for regular
expressions s and t, respectively. For the regular
expression st, construct the NFA:
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;