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 2016 EXAMINATION PDF


COURSE TITLE: Formal Languages and Automata Theory

Time: 2½ hrs
Course Credit Unit: 3

Instruction: Answer any five (5) questions. Each question carries 14 marks

1a) State Gödel incompleteness theorem) 2 marks

Goldel Incompleteness theorem basically proved that when trying to add axioms to a formal system in order to prove all true theorems within the formal system, eventually the system will become inconsistent before it becomes complete.

b) Define context-sensitive grammars ) 2 marks
We say that a grammar is context-sensitive (or type 1) if the left-hand side of a production is at least as long as the right-hand side.

c) Write short note on decision problems? ) 3 marks

Decision problems are stated as questions where the answer is binary, 0 or 1, False or True, No or yes, Reject or Accept and so forth. Generally, a decision problem states a problem and gives a candidate solution, asking if the solution solves the problem.

d) When is a formal system said to be:
i) Complete :-A formal system is said to be a complete system where all true theorems can be proved.
ii) Inconsistent:- An inconsistent formal system is a formal system where at least one false statement can be proved within the formal system.
e) Let V be a set of strings. Does V+ = V*? Justify your answer. ) 3 marks
If V is a set, then V* denotes the set of all finite strings of elements of V including the empty string which will be denoted by ε. e.g.
(0,1)* = (ε, 0, 1, 00, 01, 10, 11, 000, 001,...)
The set of all non empty strings of elements of V is denoted by V+.
Usually, V+ = V* \ (ε), but when ε ∈ V, V+ = V*. e.g. (0,1)+ = {0, 1,
00, 01, 10, 11, 000, 001,... }
but (ε, 0, 1)+ = (0,1)* = (ε, 0, 1, 00, 01, 10, 11, 000, 001,... )

2 a) List any four types of automata and state their respective recognizable language.
Deterministic finite automata (DFA) regular languages
Nondeterministic finite automata (NFA) regular languages
Pushdown automata (PDA) context-free languages
Linear bounded automata (LBA) context-sensitive language

Turing machines Recursively enumerable languages
Timed automata Deterministic Büchi automata omega limit languages
Nondeterministic Büchi automata omega regular languages
Nondeterministic/Deterministic Rabin automata omega regular languages
Nondeterministic/Deterministic Street automata omega regular languages
Nondeterministic/Deterministic parity automata omega regular languages
Nondeterministic/Deterministic Muller automata omega regular languages

b) In the context of automata theory, briefly describe the following terms:
i. Recognised language:- The recognisable languages is the set of languages that are recognised
by some automaton. For above definition of automata, the recognizable languages are regular languages.
ii. Run:- A run of the automaton on an input word w = a1, a2,...., an ∈ Σ*, is a sequence of states q0, q1, q2,...., qn, where qi ∈ Q such that q0 is a start state and qi = δ(qi-1,ai) for 0 < i ≤ n
iii. Transducer:- An automaton that produces more general output (typically a string) is called a transducer

3a) what is a sentential form? ) 2 marks
A sentential form is the start symbol S of a grammar or any string in (X U T)* that can be derived from S.

b) Consider the linear grammar: ({S, B}, {a, b}, S, {S →aS, S→B, B→bB, B→}). Give any three sentential form of this grammar ) 3 marks
Each of {S, aS, aB, abB, abbB, abb} is a sentential form
c) List and describe the various components of a formal grammar. ) 6 marks
A finite set N of nonterminal symbols, none of which appear in strings formed from G.
A finite set Σ of terminal symbols that is disjoint from N.
A finite set P of production rules, each rule of the form
where * is the Kleene sta abstract machines (or more appropriately, abstract ‘mathematical’
machines or systems) and the computational problems that can be solved using these machines.

4a) A non-deterministic finite automaton is not more powerful than a deterministic finite automaton. Discuss. (4 marks)
A state may have two or more arcs emanating from it labelled with the same symbol. When the symbol occurs in the input, either arc may be followed.
A state may have one or more arcs emanating from it labelled with (the empty string). These arcs may optionally be followed without looking at the input or consuming an input symbol.

b) Thinking of an automaton as a computer, state the way(s) it can handle non-determinism? (3 marks)
There are two ways that this could, in theory, be done:
1. When the automaton is faced with a choice, it always (magically) chooses correctly. We sometimes think of the automaton as consulting an oracle which advises it as to the correct choice.
2. When the automaton is faced with a choice, it spawns a new process, so that all possible paths are followed simultaneously.

c) State two of the ways of implementing a DFA. (2 marks)
Using a GO TO Statement
Using a CASE Statement

d) With respect to regular expressions, what is the precedence of the following operations relative to one another? (4 marks)
i) Kleene Star
ii) Concatenation
iii) Union
The unary operator * (kleene closure) has the highest precedence and is left associative. For example, a+bc* or a|bc* denotes the language {a, b, bc, bcc, bccc, bcccc, ...}.
Concatenation has a second highest precedence and is left associative.
Union has lowest precedence and is left associative

5a) Distinguish between context-free grammar and regular grammar ) 4 marks
A language defined by a DFA is a regular language while A context-free grammar is a grammar G= (X, T, S, P) for which all rules, or productions, in P have the special form A  , for A ∈ X – T and ∈X*.

b) List the three ways of defining a language (4½ marks)
Definition by Grammar
Definition by NFA
Definition by Regular Expression
c) Formally define an automaton ) 5½ marks
An automaton is represented formally by the 5-tuple ⟨Q, Σ, δ, q0, F⟩,
Q is a finite set of states.
Σ is a finite set of symbols, called the alphabet of the automaton.
δ is the transition function, that is, δ: Q × Σ → Q.
 q0 is the start state, that is, the state which the automaton is in
when no input has been processed yet, where q0 ∈ Q.
F is a set of states of Q (i.e. F⊆Q) called accept states.

6a) Describe any three of the popular variations in the definition of different components of automata.
Input: A string fed to a machine which the machine will determine whether it is part of the language that the machine was designed for
States:- A resting place while the machine reads more input, if more input is available
Transition Function:- A way for a machine to go from one state to another given a symbol from the input. Acceptance condition:- A set of states which the machine may halt in, provided it has no input left, in order to accept the string as part of the language

b) What is/are the use(s) of Greibach Normal Form? (2 marks)
Greibach Normal Form is useful for proving the equivalence of CFGs and NPDAs.
When we discuss converting a CFG to an NPDA, or vice versa,

7 b) List and describe the types of PDAs. (4 marks)
A deterministic PDA (DPDA) is one in which every input string has a unique path through the machine.

A nondeterministic PDA (NPDA) is one in which we may have to choose among several paths for an input string.

c) Distinguish between an alphabet and a language) 3 marks
In computer science and formal language, an alphabet or vocabulary is a finite set of symbols or letters, e.g. characters or digits. While a LANGUAGE can be defined as a system suitable for expression of certain ideas, facts, or concepts, which includes a set of symbols and rules to manipulate these.
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

2 Replies so far - Join Conversation

  1. I need Msc info tech past questions pls. The CIT 853 and the rest of the masters courses. Thank u

  2. It help a lot and I am happy to be part of this.


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