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
Exams With Marking Schemes
Popular Exams
Mid Term Exams
End Term 1 Exams
End Term 3 Exams
Opener Exams
Full Set Exams
Return to Question Papers