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: 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Related Searches

Objective type Questions

,

shortcuts and tricks

,

Summary

,

MCQs

,

pdf

,

Exam

,

study material

,

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

,

video lectures

,

Semester Notes

,

practice quizzes

,

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

,

ppt

,

Viva Questions

,

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

,

mock tests for examination

,

Important questions

,

Previous Year Questions with Solutions

,

Free

,

past year papers

,

Extra Questions

,

Sample Paper

;