ExamsSCHOOL OF SCIENCE AND TECHNOLOGY

National Open University Exam Past Question – CIT 342 MAY/JUNE 2012 EXAMINATION

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

14-16 AHMADU BELLO WAY, VICTORIA ISLAND LAGOS SCHOOL OF SCIENCE AND TECHNOLOGY

MAY/JUNE 2012 EXAMINATION

 

 

CIT 342 Formal Languages and Automata Theory

Time Allowed:  3 hrs

 

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

 

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

 

2a)      Distinguish between context-free grammar and regular grammar ) 4 marks b)          Distinguish between an alphabet and a language ) 3 marks

  1. c) Enumerate any two of the typical questions asked about formalism in formal language theor

) 4 marks

  1. d) Define automata theory.           ) 3 marks

 

3a)       Formally define an automaton ) 8 marks

  1. b) Describe any three of the popular variations in the definition of different components of automat

 

4a)       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:

i. Recognised language )
ii. Run ) 2 marks each
iii. Transducer )

 

5a)       State two of the ways of implementing a DFA.

  1. b) Thinking of an automaton as a computer, state the way(s) it can handle non-determinism? (3 marks)
  2. c) Is an NFA more powerful than a DFA? Explain (4 marks)
  3. d) State the precedence of the following with respect to regular expressions  ) 4 marks i) Kleene Star
  4. ii) Concatenation
YOU MAY ALSO LIKE  National Open University Exam Past Question DAM 462 October, 2013 Examination

iii)         Union

  1. iv) Parentheses

 

6a)       Formally define a PDA

  1. b) List and describe the types of PDAs.
  2. c) List the three ways of defining a language

7a)       State the Halting Problem.       ) 2marks

i) Unsolvable? )
ii) Provably unsolvable? ) 2 marks each. Total = 6 marks
iii) Undecidable? )

 

  1. b) Enumerate the mathematical concepts needed to proof the Halting Problem c)        What does it mean to say a formally stated problem is:

Related Articles

Leave a Reply

Your email address will not be published. Required fields are marked *

Close