NATIONAL OPEN UNIVERSITY OF NIGERIA

UNIVERSITY VILLAGE, PLOT 91, CASDASTRAL ZONE, NNAMDI AZIKIWE EXPRESS WAY, JABI, ABUJA.
FACULTY OF SCIENCES
MAY/JUNE 2012 EXAMINATION

COURSE CODE:                                                                              CIT342                                                                

COURSE TITLE:                                                                             Formal Languages and Automata Theory

DURATION:                                                                                     3 Hours

INSTRUCTIONS:                                                                            Answer any Five Questions.

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

Q2.a     Distinguish between context-free grammar and regular grammar                                 (4 marks)

      b.   Distinguish between an alphabet and a language                                                                          (3 marks)  

       c.   Enumerate any two of the typical questions asked about formalism in formal language theory   (4 marks)

       d. Define automata theory.                                                                                                       (3 marks)

Q3.a     Formally define an automaton                                                                                             (8 marks)

       b. Describe any three of the popular variations in the definition of different components of automata

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.     State two of the ways of implementing a DFA.

     b.    Thinking of an automaton as a computer, state the way(s) it can handle non-determinism?                                                               (3 marks)

     c.     Is an NFA more powerful than a DFA? Explain                                                                  (4 marks)

     d.    State the precedence of the following with respect to regular expressions                   (4 marks)

(i)        Kleene Star                (ii)       Concatenation

(iii)      Union                          (iv)      Parentheses

Q6a.     Formally define a PDA

      b.   List and describe the types of PDAs.

      c.    List the three ways of defining a language

Q7.a     State the Halting Problem                                                                                                    (3 marks)

1. Unsolvable?
2. Probably unsolvable?
3. Undecidable?                                                                                                    (2 marks each)

      b.   Enumerate the mathematical concepts needed to proof the Halting Problem

      c.    What does it mean to say a formally stated problem is: