# National Open University Exam Past Question – CIT 342 October, 2013 Examination

## NATIONAL OPEN UNIVERSITY OF NIGERIA CIT 342 Formal Languages and Automata Theory

14/16, Ahmadu Bello Way, Victoria Island

Course Code: CIT 342

SCHOOL OF SCIENCE AND TECHNOLOGY October, 2013 Examination

Course Title:  Formal Languages and Automata Theory

Time:              2½ hrs

Credit Unit:   3

Instruction:   Answer any five (5) questions. Each question carries 14 marks

1.(a) Within the context of computer science and formal language, Define the following term

(i) Alphabet                                                                                                                      (2 marks) (ii) String                                                                                                                          (2 marks)

(b) List and describe the general two types of string datatypes                                           (6 marks)

(c) What is the difference between Context -free grammar and regular grammar               (4 marks)

2.(a) State and discuss four examples of  analytic grammar formalisms include the following

(12 marks) (b) What is a finite state automata?                                                                                    (2 marks)

3.(a) List and describes the two types of PDA                                                                       (4 marks) (b) List seven things that define a PDA Formally                                                              (7 marks) (c) State the differences between A nondeterministic finite acceptor differs from a deterministic

finite acceptor                                                                                                                 (3 marks)

4.(a) List any four types of automata and state their respective recognizable language         (8 marks) (b) In the context of automata theory, briefly describe the following terms:                     (6 marks)

YOU MAY ALSO LIKE  National Open University Exam Past Question - EDU 752

(i)Recognized language

(ii) Run

(iii) Transducer

5.(a) Distinguish between a word and a vocabulary in formal language. Use examples to

illustrate your answer.                                                                                                   (5 marks) (b) Let V be a set of strings. Does V+ = V*? Justify your answer.                                     (3 marks)

(c) Enumerate the components for a formal grammar.                                                       (6 marks)

6.(a) State the Halting Problem.                                                                                             (2marks) (b) Enumerate the mathematical concepts needed to proof the Halting Problem

(c) What does it mean to say a formally stated problem is:                                               (6 marks) (i) Unsolvable?

(ii) Provably unsolvable?

(iii) Undecidable?

7.(a) Formally define a PDA                                                                                                  (4 marks) (b) List and describe the types of PDAs                                                                             (7 marks) (c) List the three ways of defining a language (3 marks)

Close

Close