Cisy 402:Cisy 402 Automata And Formal Languages Question Paper
Cisy 402:Cisy 402 Automata And Formal Languages
Course:Computer Science
Institution: Kenya Methodist University question papers
Exam Year:2012
KENYA METHODIST UNIVERSITY
END OF 3RD TRIMESTER 2012 (EVENING) EXAMINATIONS
FACULTY : COMPUTING AND INFORMATICS
DEPARTMENT : COMPUTER SCIENCE AND BUSINESS
INFORMATION
UNIT CODE : CISY 402
UNIT TITLE : AUTOMATA AND FORMAL LANGUAGES
TIME : 2 hours
Instructions:
• Answer question one and any other two questions.
Question One
(a) Let ? be an alphabet. (6 marks)
i. Define a deterministic finite automata on ?.
ii. Explain what is the language determined by such a finite automation.
iii. Explain why such a language is a context free language.
(b) Build A DFA corresponding to the regular expression (ab)*+a*. (6 marks)
(c) Prove by induction 12+22+32+n…+n2=n(n+1)(n+2) (5 marks)
6
(d) Find the shortest string that is not in the language represented by the regular expression a*(ab)*b* (5 marks)
(e) Define the following terms:
i. Alphabet
ii. Word
iii. String
iv. Language (8 marks)
Question Two
(a) Convert the following NFA- to DFA (10 marks)
b a
b
a
ii.
a,b
a,b
c a,b
ab
c
Question Three
(a) Describe the three properties of closure of regular expressions. (15 marks)
(b) Find a regular expression corresponding to the language of all strings over the alphabet {a,b} than contain exactly three a’s (5 marks)
Question Four
Discuss with proper examples, five types of turing machines. (20 marks)
More Question Papers