What's Popular Now

NOUN TMA Timetable with TMA Opening and Closing Date 2018

270+ Past Questions Added. Download for FREE

CIT 342 NOUN Past Questions and Answers 2013 Examination

COURSE TITLE: Formal Languages and Automata Theory


1) What do you understand by the term automata theory? (3 marks)
Automata theory is the study of abstract machines (or more appropriately, abstract ‘mathematical’ machines or systems) and the computational problems that can be solved using these machines.

2a) Define leftmost and rightmost derivation of a grammar. State the distinction between the two. ) 6 marks
b) Now consider the grammar: G = ({S, A, B, C}, {a, b, c}, S, P) whereP = {S→ABC, A→aA, A→, B→bB, B→, C→cC, C→}, derive the string abbc in a
i) leftmost derivation) 3 marks
ii) rightmost derivation ) 3 marks
c) Draw the derivation tree for the leftmost derivation in question (2b) above. ) 2 marks

3a) When is a grammar said to be in Chomsky normal form? ) 3 marks
A grammar is in Chomsky Normal Form if all productions are of the form:
A BC or A a where A, B, and C are variables and a is a terminal. Any context-free grammar that does not contain can be put into Chomsky Normal Form

b) Prove that the context-free languages are closed under the formation of union. ) 5 marks
Let G1 = (X1, T1, P1, S1) and G2 = (X2, T2, P2, S2) be context-free grammars. Without loss of generality, it can be supposed that (X1 - T1)  (X2 - T2) = . If not, then rewrite the grammar rules of one with new nonterminal symbols. Let S be another nonterminal symbol. Then set P
= P1 ∪ P2 ∪ {S S1, S S2} and G= (X1 ∪X2 ∪{S}, T1 ∪T2, P, S). It then follows that L(G) = L(G1) ∪ L(G2). P {PAGE 125}

4a) Enumerate the different ways of using a grammar. ) 4 marks
b) Briefly explain the concept of ambiguity in grammars ) 3 marks
a grammar G is ambiguous if there exists some string w ∈L(G) for which there are two or more distinct derivation trees
c) What do you understand by inherently ambiguous language? ) 2 marks
An inherently ambiguous language is a language for which no unambiguous grammar exists
d) Distinguish between a word and a vocabulary in formal language. Use examples to illustrate your answer ) 5 marks
WHILE A vocabulary (or alphabet or character set or word list) is a finite nonempty set of indivisible symbols (letters, digits, punctuation marks, operators, etc.).

5a) Define a pushdown automata (PDA) ) 4 marks

b) Proof that for any regular language there is a DPDA that accepts it (3 marks)

For any regular language there is a DPDA that accepts it.
Proof: A finite state machine is simply a PDA that does not make use of its stack. Given a regular language we can create a DPDA to accept it as follows: First create a DFA for the regular language, then change its transition labels so that instead of simply an input character, each transition is labelled with an input character and two lambdas in place of the pop and push characters.

c) When is a grammar said to be in Greibach Normal Form? (3 marks)
a grammar is in Greibach Normal Form if all productions are of the form A ax, where a is a terminal and x V*

d) State the characteristics of grammars in Greibach Normal Form ) 2 mark
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