CH4

Question 1

Define regular expression

Answer 1

is the notation for describing lexical analyzer softwares.

Question 2

What does the implementation of regular expressions require?

Answer 2

DFA simulation

Question 3

is it important and to convert NFA to DFA?

Answer 3

Yes

Question 4

Why is it important and to convert NFA to DFA?

Answer 4

Because DFA is more straightforward than NFA.

Question 5

What technique do we use to convert from NFA to DFA?

Answer 5

An algorithm of Subset Construction

Question 6

What is the general idea behind Subset Construction?

Answer 6

each DFA state correspond to a set of NFA states.

Question 7

represent NFA and DFA as a five tuple formal definition.

Answer 7

NFA =====> M = (Q,∑,∂, q0, F)

DFA====> M’ = (Q’,∑,∂’, q0’, F’)

Question 8

What is the input of the subset construction?

Answer 8

NFA “N”

Question 9

What is the output of the subset construction?

Answer 9

a DFA “D” accepting the same language as N

Question 10

T/F
the subset construction eliminates and doesnt deal with epsioln.

Answer 10

F
the subset construction deals with epsilon transitions of N properly .

Question 11

What are the operations on NFA states?

Answer 11

e-closure(s) Set of NFA states reachable from NFA state s on e-transitions alone.

e-closure(T) Set of NFA states reachable from some NFA state s in set T on e-transitions alone; =Us in T e-closure(s).

move (T,a) Set of NFA states to which there is a transition on input symbol a from some state s in T.