## NOUN Past Questions and Answers - CIT 342 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.

## 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 me how much value you got from this guide but also how much you help others to learn about NOUN Portal