ExamsSchool of Management Sciences

National Open University Exam Past Question – CIT342 OCTOBER/NOVEMBER 2014 EXAMINATION

NATIONAL OPEN UNIVERSITY OF NIGERIA CIT342 FORMAL LANGUAGES AND AUTOMATA THEORY

14-16 AHMADU BELLO WAY, VICTORIA ISLAND LAGOS SCHOOL OF SCIENCE AND TECHNOLOGY OCTOBER/NOVEMBER 2014 EXAMINATION

 

COURSE CODE:     CIT342

COURSE TITLE:    FORMAL LANGUAGES AND AUTOMATA THEORY CREDIT UNIT:        3CREDIT UNITS

TIME:                        3 HOURS

INSTRUCTION:      ANSWER ANY FOUR QUESTIONS IN ALL

 

1a.       Determine the following sets:                                                                        [8 marks]

(i)        (0, 1)

(ii)       (ε, a, ba)

(iii)      (b, aa)*

(iv)      (0,1) (ε, a, ba)

1b.       Write short note on Pushdown Automata                                                       [9.5 marks]

 

2a.       Consider the following input string: 1 0 0 1 1 1 0 0 0 1 0, using below given DFA

1. Write down the sample trace [5.5 marks]
ii. State the string status [1 mark]
iii. Give reason for the given status in question 2a(ii) above [1 mark]

 

 

 

 

 

 

 

 

 

 

 

 

 

2b. Enumerate the Algorithm for the Operation of a DFA [10 marks]
 

3a.

 

When do we say:

i.          A set is closed under an operation?

 

 

[2.5 marks]

 

3b.

ii.        A grammar G is ambiguous?

List and explain the two main Chomsky hierarchy

[5 marks]

[10 marks]

 

4a.       Write short note on Run                                                                                 [3.5 marks]

4b.       State and define 5-tuples by which an automaton is represented formally [14 marks]

 

5a. If Σ = (a, b, …, z), a = to, and b = go, then find the following:  
  (i) ba [2.5 marks]
  (ii) ab [2.5 marks]
  (iii) abba [2.5 marks]
5b. State and write short note on two types of string datatypes: [8 marks]
6a. Define the following:  
  (i)        String substitution [2.5 marks]
  (ii)       Concatenation [2.5 marks]
  (iii)      A formal grammar [2.5 marks]
6b. Describe Deterministic Finite Acceptors/Automata (DFA) [8 marks]

 

YOU MAY ALSO LIKE  National Open University Exam Past Question – CIT 341 October, 2013 Examination

Related Articles

Leave a Reply

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

Close