NFA & DFA, First and Follow, and Parsing tree

King Khalid University Subject Code: 345 CS
College of Computer Science Subject Name: Compilers
Department of Computer Science
Total Marks: /10


HOME-WORK
Instructions:
1. Write your Name, Student ID and Serial No. at the provided space.
2. This homework is for Total 10 marks.
3. Homework MUST be submitted before 21/4/2020
4. IF HOMEWORK COPIED AND SAME HOMEWORK SUBMITED MARKS WILL BE ZERO

Student Name: Mohammed Hezam Student ID: 437818630 Section. No: 2974


Q1) Consider the following grammar:

expr → expr or term | term
term → term and factor | factor
factor → not factor | ( expr ) | true | false

Find parse tree and leftmost derivation for the sentence: not ( true or false )

Parse tree:
expr

term

factor

not factor


( )
expr

expr or term

term factor

factor false


true




1

, Left derivation:
expr → term
→ factor
→ not factor
→ not ( expr )
→ not ( expr or term )
→ not ( term or term )
→ not ( factor or term )
→ not ( true or term )
→ not ( true or factor )
→ not ( true or false)


Q2) Transform the following NFA to minimum DFA:

ɛ

a
ɛ 2 3 ɛ
a b 7
Start 0 1 6
b
ɛ 4 5 ɛ
→

ɛ
1) Conversion to DFA:

ɛ-closure({0})= {0}→ A
move (A,a) ={1}
ɛ-closure({1})= {1,2,4,7}→ B
move (A,b) = Φ
move (B,a) ={3}
ɛ-closure({3})= {3,6,1,2,4,7}→ C
move (B,b) ={5}
ɛ-closure({5})= {5,6,1,2,4,7}→ D
move (C,a) ={3}
ɛ-closure({3})= →C
move (C,b) ={7,5} Input/States a b
ɛ-closure({7,5})= →D Start A B Φ
move (D,a) ={3} B C D
ɛ-closure({3})= →C Final C C D
move (D,b) ={7,5} D C D
ɛ-closure({7,5})= →D


DFA a b
a

A a B a C b D

b


2