What's Popular Now

NOUN 2018 1st International Conference on Social Sciences (ICOSS)

NOUN Exam Past Questions – CIT 342 Formal Languages and Automata Theory OCTOBER/NOVEMBER 2013 EXAMINATION

14/16, Ahmadu Bello Way, Victoria Island

CIT 342 Formal Languages and Automata Theory

Course Code: CIT 342
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)
(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 ofPDAs (7 marks)
(c) List the three ways of defining a language (3 marks)
AD: Download All New Nigerian Gospel and Hip-hop Music, Videos, Lyrics, Instrumentals and Music Performance for FREE >> LatestNigerianMusic.com

NOUN Portal Media

Teaching everything about Noun University, sharing all NOUN News & NOUNOnline Portal Guide to easy learning at the National Open University. See How to Apply for National Open University Admission. Study it, Process it and Share it.

  • Image
  • Image
  • Image
  • Image
  • Image
    Blogger Comment
    Facebook Comment

Post a Comment

We would like to learn how did this guide helped you. Share your valuable tips or Ask a question on the comment form.

P.S: Please share this guide with your friends on Facebook/ Twitter to help others to learn about NOUN Portal