NATIONAL OPEN UNIVERSITY OF NIGERIA

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

COURSE CODE:                                                                              CIT342                                                                

COURSE TITLE:                                                                             Formal Languages and Automata Theory

DURATION:                                                                                     2½ Hours

INSTRUCTIONS:                                                                            Answer any Five (5) Questions in all

Q1a.     A non-deterministic finite automaton is not more powerful than a deterministic

finite automaton. Discuss.                                                                                                     (4 marks)

      b.   Thinking of an automaton as a computer, state the way(s) it can handle

non-determinism?                                                                                                                  (3 marks)

      c.    State two of the ways of implementing a DFA                                                                   (2 marks)

      d.   With respect to regular expressions, what is the precedence of the following

operations relative to one another?                                                                                    (4 marks)

(i)        Kleene Star                (ii)       Concatenation                       (iii)      Union

Q2.a     State the formal definition of a PDA.                                                                                   (7 marks)

      b.   List and describe the types of PDAs.                                                                                   (4 marks)

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

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

       b. List the three ways of defining a language                                                                                  (4½ marks)

       c.   Formally define an automaton                                                                                          (5½ marks)

Q4.a     What is a sentential form?                                                                                                    (2 marks)

       b. Consider the linear grammar: ({S, B}, {a, b}, S, {S →aS, S→B, B→bB, B→l}).

Give any three sentential form for this grammar                                                                          (3 marks)

      c.    List and describe the various components of a formal grammar                                                (6 marks)

      d.   What do you understand by the term automata theory                                                   (3 marks)

Q5a.     State Godel incompleteness theorem                                                                                  (2 marks)

     b.    Define context-sensitive grammars                                                                                     (2 marks)

     c.     Write short note on decision problem                                                                                (3 marks)

     d.    When is a formal system said to be:

                        (i)        Complete                    (ii)       Inconsistent                                           (2 marks each)

     e.    Let V be a set of strings. Does V⁺=V^*? Justify your answer.                                             (3 marks)

Q6a.     Describe any three of the popular variations in the definition of different

components of automata.

      b.   What is/are the use(s) of Greibach Normal Form?                                                           (2 marks)

Q7a.     List any four types of automata and state their respective recognizable language.

     b.    In the context of automata theory, briefly describe the following terms:

(i)        Recognised language

(ii)       Run

(iii)      Transducer