What's Popular Now

NOUN TMA Timetable with TMA Opening and Closing Date 2018

270+ Past Questions Added. Download for FREE

NOUN Exam Past Questions - CIT 342 Formal Languages And Automata Theory MARCH/APRIL 2016 Examination

MARCH/APRIL 2016 Examination
COURSE TITLE: Formal Languages And Automata Theory

Instructions: Answer any 5 questions. Each question carries 14 marks
1a. state Gödel incompleteness theorem 2marks
b. define context-sensitive grammars 2marks
c. write short note on decision problems 3marks
d. When is a formal system said to be:
i. Complete?
ii. Inconsistence? 2marks
e. Let V be a set of strings. Does V+=V*? justify your answer 3marks

2a. List any 4 types of automata and state their respective recognizable language
b. in the context of automata theory. Briefly describe the following terms
i. Recognized Language
ii. Run
iii. Transducer

3a. what is sentential form? 2marks
b. consider the linear grammar ({S,B.{a,b},S, {S—aS, S—B,B—bB,B---b}}) give any three sentential form of this grammar 3marks
c. List and describe the various components of a formal grammar 6marks
d what do you understand by the term automata theory? 3marks

4a. A non-deterministic finite automaton is not more powerful than a determine finite automaton. Discuss. 4marks
b. thinking of an automation as a computer, state the ways it can handle non-determinism? 3marks
c. state two of the ways of implementing a DFA 2marks
d. with respect to regular expressions, what is the precedence of the following operations relative to one another? 4marks
i. Kleene Star
ii. Concatenation
iii. Union

5a. Distinguish between context-free grammar and regular grammar 4marks
b. List the three ways of defining a language 4marks
c. formally define an automation 5marks

6a. Describe any three of the popular variation in the definitions of different components of Automata
b.What is/are the use(s) of Greibach Normal Form? 2marks

7a. state the formal definition of PDA 7marks
b. List and describe the types of PDAs. 4marks
c. Distinguish Between an alphabet and a language 3marks
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