WHAT'S TRENDING

NOUN TMA Portal Login Page - National Open University of Nigeria TMA

Noun TMA Portal login Page link was more visible on the former noun student portal login website ( www.noun.edu.ng ) - if you could remembe...

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

NATIONAL OPEN UNIVERSITY OF NIGERIA 
14/16, Ahmadu Bello Way, Victoria Island

CIT 342 Formal Languages and Automata Theory

Course Code: CIT 342
SCHOOL OF SCIENCE AND TECHNOLOGY October, 2013 Examination
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)
SHARE

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

I would like to learn how did this guide helped you. Share your valuable tips, and comments on the comment form.

P.S: It’s a pleasure to me if you share this guide with your relatives and friends on any social network. That will not only show me how much value you got from this guide but also how much you help others to learn about NOUN Portal

Here's What to Read Today

Recent Posts Widget