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.

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.

**You Have A Voice, We Have A Platform.** Now, You Can Promote Your Music, Video and Events for
FREE!!! Click on link to Get Started >> LatestNigerianMusic.com

## Post a Comment

I would like to learn how did this guide helped you. Share your valuable tips, and comments on the comment form.

P.S: It’s a pleasure to me if you share this guide with your relatives and friends on any social network. That will not only show how much value you got from this guide but also how much you help others to learn about NOUN Portal