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) Write context free grammar for the following regular expression:
(a(a|b)+b)*b
S→ AC
A→ aBb | ϵ
B→ aB | bB | a | b
C→ b
Q2) Transform the following regular expression to NFA:
(a(a|b)+b)?
ϵ
a
ϵ 3 4 ϵ
2 2 b
Start ϵ a 7 82
0 1 2 2 22
2 2 2
ϵ 5 b 6 ϵ
2 2
ϵ
Q3) What is the regular expression of the following NFA?
ɛ
a
ɛ 2 3 ɛ
b ɛ
Start 0 1 6
→ b
ɛ 4 5 ɛ
ɛ
b(a+|b+)?
1
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) Write context free grammar for the following regular expression:
(a(a|b)+b)*b
S→ AC
A→ aBb | ϵ
B→ aB | bB | a | b
C→ b
Q2) Transform the following regular expression to NFA:
(a(a|b)+b)?
ϵ
a
ϵ 3 4 ϵ
2 2 b
Start ϵ a 7 82
0 1 2 2 22
2 2 2
ϵ 5 b 6 ϵ
2 2
ϵ
Q3) What is the regular expression of the following NFA?
ɛ
a
ɛ 2 3 ɛ
b ɛ
Start 0 1 6
→ b
ɛ 4 5 ɛ
ɛ
b(a+|b+)?
1
