# Theory of Automata and Computation – Past (old) Papers for BSCS/MCS

Past Guess Paper of Theory of Automata and Computation

## Guess Paper 1 : Theory of Automata and Computation

Course Code: Confidential |
Course Title: Theory of Automata and Computation |

Teacher’s Name: Confidential |
Total Marks: 30 |

Date & Time: Confidential |
Total Time: 2 Hours |

Student’s Name: |
Reg. No: |

__Question #1:__** 8 marks**

Built the CFG for the language of a^{n}b^{2n}

Supported strings like L={abb,aabbbb,aaabbbbbb,……}

__Question #2:__** 8 marks**

Built the PDA for the language of a^{n}b^{4n}

Supported strings like L={abbbb,aabbbbbbbb,aaabbbbbbbbbbbb,……}

__Question #3:__** 8 marks**

Built the Turing machine for the language of a^{n}b^{n }, where a=b.

Supported strings like L={abb,aabbbb,aaabbbbbb,……}

__Question #4:__** 6 marks**

Write the regular expression for the language of odd length strings

Supported strings like L={a,aba, aabaa, aabbbab,……}

### Theory of Automata and Computation – Paper 2 for MCS

Course Code: Confidential |
Course Title: Theory of Automata and Computation |

Teacher’s Name: Confidential |
Total Marks: 30 |

Date & Time: Confidential |
Total Time: 2 Hours |

Student’s Name: |
Reg. No: |

__Question #1:__** 6 marks**

Built the CFG for the language of a^{m}b^{n}, Where m<n

Supported strings like L={abb,aabbb,aaabbbbbb,……}

__Question #2:__** 6 marks**

Built the PDA for the language of a^{n}b^{3n}

Supported strings like L={abbb,aabbbbbb,aaabbbbbbbbb,……}

__Question #3:__** 6 marks**

Built the Turing machine for the language of a^{m}b^{n}, Where m>n

Supported strings like L={aab, aaaaabb, aaaaabbb, aaaabb,……}

__Question #4:__** 6 marks**

Write the regular expression for the language of even length strings

Supported strings like L={aa,bb, abba, baba,bbbb, ……}

__Question #5:__** 6 marks**

Built the PDA for the language of a^{n}b^{n}

Supported strings like L={ab, aabb, aaabbb,……..}

Past Guess Paper of Theory of Automata and Computation

## Guess Paper 2 : Theory of Automata Past Papers

**University Name – Confidential**

**NOTE: ***Q.1 is compulsory, attempt any four questions from the remaining. All questions carry equal marks.* *Phones and other Electronic Gadgets are not allowed.*

Time Allowed: __3 hours__

Examination: __Final, Fall – 2020__

Total Marks: __70, Passing Marks (35)__

Q1. This question is compulsory. (Marks 30)

I. Write True or False for the following

i. The Palindrome language over the alphabet set Σ={0,1} can easily be expressed by a CFG but it is impossible to represent the language by an FA or a Regular Expression.

ii. In a Parse tree, the symbols at the leaves are always non-terminals.

iii. There always exists an NFA for a regular language L that can be represented correctly by a certain DFA say A.

iv. The transition table drawn from any NFA must have exactly one state for all values of the transition function δ and all input symbols of a given alphabet set Σ.

v. In a PDA (Push Down Automata) the state of the PDA can be changed e.g from qi toqj even by consuming no input symbol from the input string.

II. Pick the suitable from the following multiple choices.

i. A move of the Turing Machine is a function of ……..

(a) The state of the finite control (ie. Control unit) (b) The tape symbol scanned

(c) both (a) and (b) (d) neither (a) nor (b)

ii. ……… is/are used in order to infer/map/decide whether an input string belongs to a certain Language L represented by a CFG.

(a) Left most derivation (b) Right most derivation

(c) Parse Trees (d) all (a), (b) and (c)

iii. In Parse Tree the root node is always ……….

(a) A non-terminal (b) Start symbol S represented by the first production the CFG

(c) A terminal (d) both (a) and (b)

iv. In PDA the input string is accepted when ………..

(a) One of the Final States occur (b) The stack becomes empty

(c) The stack becomes full (d) both (a) and (b)

v. In any Finite Automata the minimum number of total states are at least ………

(a) 1 (b) 2

(c) 0 (d) 3

Q.2) (Marks 3+4+3=10)

I. Explain FA and its different types (DFA, NFA, є-NFA)?

II. Design a DFA for the Language

L={w/w is of even length and begins with 01}

III. Write the transition table for the DFA produced in (B)

Q.3) (Marks 2+4+2+2=10)

A. What is Context Free Language (CFG) representation of a Language?

B. Write a CFG for the Language L over the alphabet ∑ ={ (, )} where the words are balanced parenthesis. e.g ( ( ) ) ( ), ( ) ( ( ) ) .

C. Construct a Parse tree showing that the string ( ) ( ) ( ) is mapped by the CFG in (II)

D. What is the necessary condition when a CFG is called an Ambiguous grammar?

Q.4) (Marks 4+6=10)

I. What is Push Down Automata?

II. The following transition diagram for the PDA of the Language

Lwwr={wwR, w Є(0,1)*} is shown. Here an accepting word is made up of the two

strings where the first string is the reverse of the other (even length palindrome). e.g.

1001, 110011, 0 0, 1111 .

Task: Given the string 1111 write two sets of Moves for Accepting this string as a word of the Language Lwwr.

Q.5) (Marks 3+4+3=10)

I. What is a Turing Machine?

II. Design a Turing Machine of the One’s Complement. Write down the state transition diagram.

III. Write the changes occurring on the tape when converting input 100110 into one’s complement by the TM designed in (II). The input string is shown on the tape as in the following.

Q.6) (Marks 3+4+3=10)

Given the alphabet set Σ={0,1} Write Regular Expression for the following languages

I. Language L1 where all words must start with 0 and end with 1.

II. Language L2 where all words must contain 11.

III. Language L3 where all words either start with 1 or end with 01 or both.

Q.7) (Marks 4+4+2=10)

I. What is Right Most and Left Most derivations in a CFG.

II. Map the words w1=abba and w2=baab on the following CFG using Left Most derivation.

S → ε

S → aSa

S → bSb

III. What language is represented by above CFG, G={{S},{a,b},A,S}

## Guess Paper 3 : Theory of Automata Past Papers

**University Name – Confidential**

**NOTE: ***Q.1 is compulsory, attempt any four questions from the remaining. All questions carry equal marks.* *Phones and other Electronic Gadgets are not allowed.*

Time Allowed: __3 hours__

Examination: __Final, Fall – 2020__

Total Marks: __70, Passing Marks (35)__

Q.1 (a) Fill in the blanks with appropriate choice.

1. A set of strings that corresponds to a pattern is called ___________.

a.Language. b.Regular expression. c.Token.

2. A string that has no letters is called __________.

a.Empty string. b.Null string. c.Both of them.

3. Two strings written side by side to form a new longer string is called ___________.

a.String merging. b.String concatenation. c.Both of them.

4. Given an alphabet Σ, the language that any string of characters from Σ is a word, even the null string is called _______________.

a.Positive closure. b.Null closure. c.Kleene closure.

5. (a|b)+ is called _________.

a. Alternation.

b. Kleene clouser.

c. Positive clouser.

6. A rule that specifies the structure of a token in a language is called _________ .

a.Pattern. b.Definition. c.Grammar.

7. A FSM in which edges can be labeled with empty (λ) is called __________.

a.Non-deterministic finite automata. b.Deterministic finite automata.

c.None of them.

8. If a string consists of both terminal and non-terminal symbols is called _____________ form of the grammar.

A.Sentence. b.Sentential. c.Both of them.

9. Replacing a non-terminal with the right hand side of the corresponding rule in the grammar is called ____________.

a.Derivation. b.Refinement. c.Evaluation.

10. FIRST and FALLOW sets are used in the construction of ______________.

a.Syntax diagram. b.Pumping lemma. c.Parse table.

(b) State that which of the following statements are true and false.

1. A language which cannot be described by a regular expression is called non-regular language.

2. BNF notations are used to describe the regular expressions.

3. The output of syntax analyzer is stream of tokens.

4. All words with an even number of symbols and that returns 1 is called EVEN-EVEN.

Q.2 (a) Let S = { ab, bb }and T = { ab, bb, bbb }. (8)

1. Show that S* ≠ T *.

2. (S+)+ = S+.

(b) Define the followings: (6)

1. Alphabet.

2. Language.

3. Words.

Q.3 (a) Let = { a, b, c } . Write regular expressions for the following statements. (8)

1. All strings of a’s and b’s that have at least two letters.

2. All strings of a’s and b’s that at some point contain a double letter i.e aa or bb.

3. All strings of a’s and b’s that have at least two a’s in them.

4. All strings of a’s and b’s in which the letter b is never continuously tripled. This means that no word contain the substring bbb.

(b) Describe the language specified by the following regular expressions. (6)

1. ( a | b )* ( ab | ba )

2. (a ( a | b )* a) | (b ( a | b )* b)

3. b* ab* ab* ab*

Q.4 Consider the following NFA machine.

(a) Write the regular expression for the above machine. (4)

(b) Convert the above machine into DFA using ε – Closure method and describe each step. (10)

Q.5 (a) What is Finite Automata, describe the different types of Finite Automata. (6) (b) Let L = { a, b }. Answers the followings. (8)

1 Build FA that accepts only those words that do not end with ba.

2. Build FA that accepts only those words that start with aa and end with bb or vice versa.

3. Build FA that accepts only those words that contain exactly two a’s.

4. Build FA that accepts only the words baa, ab and abb. No other words.

Q.6 (a) What is grammar, explain the context free grammar (CFG) in detail. (5)

(b) Describe the steps of converting regular expressions into CFG. (5) (c) Consider the following grammar.

S aS | bb

Prove that this generates the language defined by the regular expression a*bb. (4)

Q.7 (a) What is meant by ambiguity in a CFG, show that the following grammar is ambiguous for the string A = B + C * A by deriving more than one parse trees. (8)

<assign> <id> = <expr>

<id> A | B | C

<expr> <expr> + <expr> | <expr> * <expr>

| (<expr>) | <id>

(b) What is meant by left recursion in a CFG, how it can be removed from a CFG and show removal of left recursion from the following CFG. (6)

E à E + T

E à T

Q.8 Write short notes on any TWO of the followings.

1. Pumping Lemma.

2. Turing Machine.

3. Pushdown Automata.

## Guess Paper 4 : Theory of Automata Past Papers

**University Name – Confidential**

**NOTE: ***Q.1 is compulsory, attempt any four questions from the remaining. All questions carry equal marks.* *Phones and other Electronic Gadgets are not allowed.*

Time Allowed: __3 hours__

Examination: __Final, Fall – 2019__

Total Marks: __70, Passing Marks (35)__

Q.1 (a) Fill in the blanks with appropriate choice.

1. Strings that are permissible in the language are called __________.

a. Alphabets.

b. Sentence.

c. Words.

2. The operation in which two strings are written side by side to form a new longer string is is called _________.

a. Extension.

b. Enhancement.

c. Concatenation.

3. A system which convert itself from one given state to some particular other state on reading one particular input instruction is called _________ system.

a. Intelligent.

b. Deterministic.

c. Non-deterministic.

4. A generalization that enables us to prove that certain other languages are also non-regular is called ____________ .

a. Push-Down automata.

b. Pumping lemma..

c. Chomsky hierarchy.

5. Rules that involves the semantic of words we call ________ and rules that do not involve the meaning of words we call _________.

a. Syntax, Semantics.

b. Semantics, Syntax.

c. Regular, Non-regular.

6. The sequence of application of the rules that produces the finished string of terminals form the starting symbol is called _________ .

a. Production.

b. Derivation.

c. Grammar.

7. Pushdown automata makes use __________ data structure.

a. Linked lists.

b. Stack.

c. Queue.

8. If a string consists of only terminal symbols is called __________ form of the grammar.

a. Sentence.

b. Sentential.

c. Both of them.

9. The generalized form of tree that represents the grammatical phrases of the source program is called _______.

a. Syntax Tree.

b. Annotated Tree.

c. Parse Tree.

10. __________ is called Context Free Grammar.

a. Type – 0.

b. Type – 1.

c. Type – 2.

(b) State that which of the following statements are true and false.

1. The method of proving that something exists by showing how to create it is called proof by constructive algorithm.

2. Regular expressions specifies the structure of token thus we can say that regular expressions specifies the lexeme for tokens.

3. A successful path through a transition graph is a series of edges forming a path beginning at some start state and ending at a final state.

4. Kleene’s theorem says all of the three methods of defining languages are not equivalent.

Q.2 Differentiate between the followings. (14)

1. Lexical errors and Syntax errors.

2. Lexeme, Pattern and Token.

3. NFA and DFA.

4. Regular and Non-regular language.

5. Left-most derivation and Right-most derivation.

Q.3 (a) Let = { a, b, c } . Write regular expressions for the following statements.. (6)

1. All strings of a’s and b’s that have at least two letters.

2. All strings of a’s and b’s that at some point contain a double letter i.e aa or bb.

3. All strings of a’s and b’s that have at least two a’s in them.

(b) Describe the language specified by the following regular expressions. (8)

1. ( a | b )* a ( a | bbbb ).

2. ( a ( a | bb )* )*.

3. ( a(aa)*b(bb)*)*.

4. ( b(bb)*)*(a(aa)*b(bb)*)*(a(aa)*)*.

Q.4 (a) What is Finite Automata, describe the different types of Finite Automata. (6) (b) Let L = { a, b }. Answers the followings. (8)

1 Build NFA that accepts only those words that do not end with ba.

2. Build NFA that accepts only those words that start with aa and end with bb or vice versa.

3. Build NFA that accepts only those words that contain exactly two a’s.

4. Build NFA that accepts only the words baa, ab and abb. No other words.

Q.5 Consider the following NFA machine. Answer the following questions.

(a) Write the regular expression for the above machine. (2)

(b) Convert the above machine into DFA through E – Closure method and describe each step. (12)

Q.6 (a) What is grammar, Explain the Context Free Grammar in detail (5)

(b) Describe the steps of converting Regular Expressions into CFG. (5) (c) Consider the following grammar.

S aS | bb

Prove that this generates the language defined by the regular expression a*bb. (4)

Q.7 (a) What is meant by Push Down Automata (PDA), explain the algorithm for converting a CFG

into PDA. (8)

(b) Covert the following CFG into PDA. (6)

S AB

A BB

B AB

A a

B a

B b

Where S is the starting symbol of Grammar.

Q.8 Write short notes on any TWO of the followings.

1. Pumping Lemma.

2. Moore Machine.

3. Turing Machine.

## Past Paper of theory of Computation 2021

Program : MS(CS)

Paper: Theory of Computation

Total Marks: 40

**Question #1:**

Suppose you are assigned a task to build a computational machine to check that whether a string that belongs to a given language is L={ a^{n} b^{n} c^{n} d^{n} }. You are required to design this machine so that some intimation message for any security system for this pattern. You are required to design this machine and check its decidability by taking any sample string from the given language.

**Question#2: **

Convert the following C.F.G to C.N.F (Chomsky Normal Form) and then built a memory-based computational machine from the converted C.N.F and validate it.

- S->
*aYYY*|*bXXXX* *S-> a*|*aS*|*bYYY**Y->b*|*bS*|*aXX*

**Question#3:**

Design a sample language and it’s an equivalent memory-based computational machine to evaluate the arithmetic expression 4+5*6-7. Validate the machine using any valid as well as invalid sample string.

**Question#4:**

Suppose two different teams are working on the validation of authentication of a cybersecurity application by considering some complex patterns. One team is considering patterns

from the language *L *(*a *(*b ** +*c**)*d *) while the other team considers the patterns from

*L *(*ab *** d *+* ac *** d *) . It is doubted that both teams have actually considered the same patterns and

validation is not reliable. You are required to identify that whether both languages are the same or different.