Bct2311:Compiler Construction Question Paper
Bct2311:Compiler Construction
Course:Computer Technology
Institution: Meru University Of Science And Technology question papers
Exam Year:2013
1
QUESTION ONE – 30 MARKS
a. Discuss two ways of accepting an input string by pushdown automata. (4 Marks)
b. Define the following terms and give an example of each. (2 Marks)
i. Alphabets
ii. Strings
c. Draw a (state) transition diagram of the DFA below. (3 Marks)
d. What is decidability and undecidability of problems? (4 Marks)
e. What is Turing test? (2 Marks)
f. What is an accepting or rejecting state of a finite automa? (2 Marks)
g. Outline the importance of studying automata theory. (3 Marks)
h. Give an application of context free grammars. (4 Marks)
i. Discuss context sensitive grammars and context free grammars. (4 Marks)
j. Let A – {a, b, c}, B = {b, d, c}. Find (2 Marks)
i. AnB
ii. A?B
2
QUESTION TWO – 20 MARKS
a. Convert the following NFA to DFA (10 Marks)
b. Describe the three properties of closure of regular expressions. (10 Marks)
QUESTION THREE – 20 MARKS
a. Give DFA for recognizing the language of all binary strings ending in 0110. (4 Marks)
b. With the transition table below, produce a DFA (12 Marks)
States a b c
0 0 0 0
1 2 0 0
2 0 3 0
3 0 0 4
4 2 0 4
q0 is 0 and F = {3, 4}
c. Find a regular expression corresponding to the language of all strings over the alphabet {a, b} that
contain exactly three a’s. (4 Marks)
3
QUESTION FOUR – 20 MARKS
a. Describe a deterministic one-tape turing machine and how it works. (4 Marks)
b. Describe the Chomsky normal form. (2 Marks)
c. Calculate how many words there are in the following languages. List three elements in each of them.
Which language contains ??? (4 Marks)
S*, where S = {a, b, c}
wE S*||w|=},
where S={a, b}
{w E S*||w| = 4}, where S = {a, b}
{an b/n is prime}
d. Find regular expressions for the following NFAs (10 Marks)
QUESTION FIVE – 20 MARKS
a. Discuss the four characteristics of finite automata. You may use diagrams where possible. (8 Marks)
b. Discuss the following: (4 Marks)
c. What is decidability and undesirability of problems? (2 Marks)
d. Given the following:
?? = {a}
Productions:
S as
S ?
Trace the execution of applying rule 1 three times and rule 2 once. (4 Marks)
More Question Papers