NATIONAL OPEN UNIVERSITY OF NIGERIA
14-16 AHMADU BELLO WAY, VICTORIA ISLAND LAGOS
MARCH/APRIL 2016 EXAMINATION
SCHOOL OF SCIENCE AND TECHNOLOGY
COURSE CODE: CIT342
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⟩,
where:
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.
OCTOBER/NOVEMBER 2014 EXAMINATION
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]
q0 1 q1 0 q3 0 q1 1 q0 1 q1 1 q0 0 q2 0 q0
ii. State the string status [1 mark]
Since q0 is a final state, the string is accepted.
iii. Give reason for the given status in question 2a(ii) above [1 mark]
the end state (qo) is the final state
2b. Enumerate the Algorithm for the Operation of a DFA [10 marks]
• Start with the “current state” set to the start state and a “read head” at the beginning of the input string
• while there are still characters in the string
• Read the next character and advance the read head
• From the current state, follow the arc that is labelled with the character just read; the state that the arc points to becomes the next current state
• When all characters have been read, accept the string if the current state is a final state, otherwise reject the string.
3a. When do we say:
i. A set is closed under an operation? [2.5 marks]
A set is closed under an operation if, whenever the operation is applied to members of the set, the result is also a member of the set.
ii. A grammar G is ambiguous? [5 marks]
A grammar G is ambiguous if there exists some string w ∈L(G) for
which:
there are two or more distinct derivation trees, or
there are two or more distinct leftmost derivations, or
there are two or more distinct rightmost derivations.
3b. List and explain the two main Chomsky hierarchy [10 marks]
Two important types are context-free grammars (Type 2) and regular grammars (Type 3). The languages that can be described with such a grammar are called context-free languages and regular languages, respectively.
4a. Write short note on Run (previously answered) [3.5 marks]
4b. State and define 5-tuples by which an automaton is represented formally [14 marks]
An automaton is represented formally by the 5-tuple ⟨Q, Σ, δ, q0, F⟩,
where:
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.
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]
Fixed length strings and variable length strings
Fixed length strings which have a fixed maximum length and which use the same amount of memory whether this maximum is reached or not, and variable length strings whose length is not arbitrarily fixed and which use varying amounts of memory depending on their actual size.
6a. Define the following:
(i) String substitution:- [2.5 marks]
A string substitution or simply a substitution is a mapping f that maps letters in Σ to languages (possibly in a different alphabet).
(ii) Concatenation:- [2.5 marks]
Concatenation is an important binary operation on Σ*. For any two strings s and t in Σ*, their concatenation is defined as the sequence of characters in s followed by the sequence of characters in t, and is denoted st.
(iii) A formal grammar [2.5 marks]
A formal grammar (sometimes simply called a grammar) is a set of rules for forming strings in a formal language.
6b. Describe Deterministic Finite Acceptors/Automata (DFA) [8 marks]
DFAs are: Deterministic i.e. there is no element of choice
Finite i.e. only a finite number of states and arcs
Acceptors i.e. produce only a yes/no answer
A DFA is drawn as a graph, with each state represented by a circle.
October, 2013 Examination
Course Code: CIT 342
1.(a) Within the context of computer science and formal language, Define the following term
(i) Alphabet (previously answered) (2 marks)
(ii) String:- a string is a finite sequence of symbols that are chosen from a set or alphabet. (2 marks)
(b) List and describe the general two types of string datatypes (previously answered)
(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)
Examples of analytic grammar formalisms include the following:
1. The Language Machine directly implements unrestricted analytic grammars. Substitution rules are used to transform an input to produce outputs and behaviour. The system can also produce the
lm-diagram which shows what happens when the rules of an unrestricted analytic grammar are being applied.
2. Top-down parsing language (TDPL): a highly minimalist analytic grammar formalism developed in the early 1970s to study the behaviour of top-down parsers.
3. Link grammars: a form of analytic grammar designed for linguistics, which derives syntactic structure by examining the positional relationships between pairs of words.
4. Parsing expression grammars (PEGs): a more recent generalisation of TDPL designed around the practical expressiveness needs of programming language and compiler writers.
(b) What is a finite state automata? (2 marks)
An FSA is a virtual device that manipulates a candidate string, one character at a time, and determines whether that string is in the language implemented by the machine. The simplest state machine reads the string exactly once, and has no memory, only registers. It is therefore a finite state automaton.
An FSA is defined by a set of states and a transition function that maps state/input pairs into states. In this state, reading this character, move to that state and advance to the next character..
3.(a) List and describes the two types of PDA (previously answered)(4 marks)
(b) List seven things that define a PDA Formally (7 marks)
Formally, a PDA is defined as a collection of seven things:
1. an alphabet of input letters
2. an input tape containing an input string followed by
3. an alphabet of stack letters
4. a pushdown stack, initially empty
5. one start state
6. a set of accept states
7. a transition function
(c) State the differences between A nondeterministic finite acceptor differs from a deterministic
finite acceptor (3 marks)
A nondeterministic finite acceptor differs from a deterministic finite acceptor in two ways:
1. The transition function is single-valued for a DFA, multi-valued for an NFA.
2. An NFA may have -transitions.
6.(a) State the Halting Problem. (2marks)
The Halting Problem says that no computer program or Turing machine can determine if ALL computer programs or Turing machines will halt or not halt on ALL inputs.
(b) Enumerate the mathematical concepts needed to proof the Halting Problem
The mathematical concepts we need are:
Proof by contradiction: Assume a statement is true, show that the assumption leads to a contradiction. Thus the statement is proven false.
Self referral: Have a computer program or a Turing machine operate on itself, well, a copy of itself, as input data. Specifically we will use diagonalisation, taking the enumeration of Turing machines and using TMi as input to TMi.
Logical negation: Take a black box that accepts input and outputs true or false, put that black box in a bigger black box that switches the output so it is false or true respectively.
(c) What does it mean to say a formally stated problem is: (6 marks)
(i) Unsolvable?
A formally stated problem is Unsolvable if no Turing machine exists to compute the solution.
(ii) Provably unsolvable?
A formally stated problem is provably unsolvable if it can be proved no Turing machine exists to compute the solution.
(iii) Undecidable?
A formally stated problem is Undecidable if no total recursive function and thus, no Turing machine that always halts can be constructed to the problem, usually true or false.
JUNE/JULY 2013
COURSE CODE: CIT342
4d) 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.
JANUARY/FEBRUARY 2013 EXAMINATION
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