Q1
A) NAME THE FIVE STEPS OF THE COMPILATION PROCESS WITH I/O OF EACH STEP?
B) WHAT IS BACKTRACKING AND WHY DO WE HAVE TO REMOVE IN A TOP-DOWN PARSER ?
C) CAN THE LBA (LINEARLY BOUNDED AUTOMATON) RECOGNIZE REGULAR LANGUAGES? WHY?
Q2
FOR THE FOLLOWING NFA TRANSITION FUNCTIONS, CONVERT IT INTO A DFSM USING THE SUBSET METHOD
a b EPSILON
1 {4} { } {2,3}
2 { } {3} { }
3 { } {1 } {4 }
4 { 2} { } {3}
Q0=1 AND F= {4}
USE A SCRATCH PAPER TO COME UP WITH AN ANSWER, IF YOU WANT AND FILL IN THE FOLLOWING:
- E-CLOSURES FOR EACH STATE
- INPUT ALPHABETS I = { ? }
- Q (STATES) = { ? }
- STARTING STATE = ?
- ACCEPTING STATES = { ? }
- TRANSTION FUNCTIONS IN THE FORM OF (Q, I ) -> Q E.G., ([12], A) -> [123]
or the table (if you want)
Q3
IF INPUT ALPHABETS ARE {0, 1}, WRITE A RE WHOSE LANGUAGE IS ALL STRINGS IN WHICH ALL STRINGS CONTAIN
EXACTLY TWO 0’S AND ONE OR MORE 1’S
Q4
find first sets for each non-terminal symbol, i.e., D, O, N, E
Show all works
D->one
O->xy | b | epsilon
N-> Ez | cd | epsilon
E-> m | fgD | epsilon
Q5
remove all left recursions ( Immediate and non-immediate ) from the productions
S-> S % T
S-> S * T
S-> T
T-> T & B
T-> b
T-> B
T-> S
Sample Solution