NATIONAL OPEN UNIVERSITY OF NIGERIA

UNIVERSITY VILLAGE, PLOT 91, CASDASTRAL ZONE, NNAMDI AZIKIWE EXPRESS WAY, JABI, ABUJA.
FACULTY OF SCIENCES
OCTOBER 2013 EXAMINATION

COURSE CODE:                                                                              CIT342                                                                

COURSE TITLE:                                                                             Formal Languages and Automata Theory

DURATION:                                                                                     2½ Hours

INSTRUCTIONS:                                                                            Answer any Five Questions

Q1a.     Within the context of computer science and formal language,

Define the following term

1. 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)       

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

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

Q3.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)

Q4.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)

(i)        Recognized language                       

(ii)       Run

(iii)      Transducer

Q5a.     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)

Q6a.     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?

Q7.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)