## NOUN Past Questions and Answers - CIT 342 October, 2013 Examination

**Course Code**: CIT 342

**Course Title:**Formal languages and Automata Theroy

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 thelm-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.

## 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