TOC Summer 2022 Previous Year Paper Solutions

Q.1

(a) Define: Set, Subset, Complement. (3 marks)

Set

Set is a collection of objects. the objects are the elements such as 1,2,3 etc.

eg. A = { 1,2,3,4 }

Here A is called as the set which is the collection of elements 1,2,3,4

Subset

A set A is called the subset of B when all the elements of set A are present in Set B but the reverse is not true.

eg:- A={ 1,2,3 } B={ 1,2,3,4,5 }

Here A is the subset of B as all the elements of A are present in B but all elements of B are not present in A

Complement

Complement of a set A means the elements which are present in universal U but not in set A. It is denoted as $\bar{A}$

eg : A = { 1,2,3 } U = { 1,2,3,4 }

$∴ \bar{A}={4}$

(b) Write and explain the principle of mathematical induction using example. (4 marks)

PMI with example

PMI means principle of mathematical induction.

There are 3 steps in PMI

1. Basis of Induction
2. Hypothesis
3. Induction step

In the first step we assume the value of n=1, in 2nd step we assume value of n=k, & in industion step we assume value of n = k+1

let us understand this with an example

suppose;

1+2+3+…+n = $n^2$

using PMI

step 1:-

n=1

LHS = 1

RHS = $n^2 = 1^2 = 1$

LHS = RHS

step 2:-

n = k

$1+2+3+...+k = k^2$ —-1

step 3:-

n = k + 1

$1+2+3+...+k+(k+1)$$∴ k^2 + (k+1)$ , from eg 1 $∴ k^2 + k + 1$$∴ (K+1)^2$

= RHS

Hence LHS = RHS

Hence in this way we can solve examples of PMI

(c) Draw Finite automata for following regular expression: (7 marks)

1. (0+1)∗(1 + 00)(0+1)∗

   

2. (111+100)∗0

   

Q.2

(a) Explain Regular language & Regular expressions. (3 marks)

Regular language is the sentential form of a language.

eg.

A language of all string that end with 01

A language of all string that end with abb over E = { a,b }

A language of all string that start with 1 and end with 0 over E = { 0,1 }

Regular Expression means any language written in expressional form

eg.

Langauge of all string that end with 01. RE = $(0+1)* \ \ \ 01$

Language of all strings that end with abb over E = { a,b } RE = $(a+b)* \ \ abb$

Language of all strings that start with 1 and end with 0 over E = { 0,1 } RE = $1\ \ \ (0+1)* \ \ 0$

(b) Find a regular expression corresponding to each of the following subsets of {0,1}*

1. the language of all strings that do not end with 01

   RE = $(0+1)* \ \ (00+11+10)$

2. the language of all strings that begin with or end with 00 or 11

   RE =$(00+11)\ \ (0+1)$

(4 marks)

(c) Prove Kleene’s theorem part-1. (7 marks)

Refer [ https://truptikodinariya.wordpress.com/wp-content/uploads/2014/03/kleene_s-theorem.pdf ]

OR

(c) Explain procedure to minimize finite automata. (7 marks)

Refer [ https://www.javatpoint.com/minimization-of-dfa ]

Q.3

(a) Define Context free grammar & context free language. (3 marks)

A Context-Free Grammar (CFG) is a formal grammar that is used to generate all possible strings in a given formal language. CFGs are composed of a finite set of grammar rules that can be applied regardless of the context of a nonterminal; this means the rules apply independently of the surrounding symbols or elements. A CFG is typically defined by a tuple (𝑁,Σ,𝑃,𝑆), where:

• 𝑁 is a set of nonterminal symbols, which are placeholders for patterns of strings.
• Σ is a set of terminal symbols, which form the content of the strings.
• 𝑃 is a set of production rules that describe how the nonterminals can be combined with terminals and other nonterminals to generate strings.
• 𝑆 is the start symbol, a special nonterminal from which all strings in the language can be derived.

A Context-Free Language (CFL) is a type of formal language that can be generated by some CFG.

(b) Write CFG for following (4 marks)

1. $L = {a^i \ b^j \ c^k \ | \ i=j \ \ or \ \ j=k}$

   G=(N,Σ,P,S) where:

   • N is the set of nonterminal symbols.
   • Σ is the set of terminal symbols.
   • 𝑃 is the set of production rules.
   • 𝑆 is the start symbol.

   Nonterminal Symbols:

   • 𝑆: Start symbol.
   • 𝐴: Generates strings where the number of a's equals the number of b's.
   • 𝐵: Generates strings where the number of b's equals the number of c's.
   • 𝐶: Helper symbol to generate strings according to the i=j or j=k rule.

   Terminal Symbols:

   • 𝑎,𝑏,𝑐

   Production Rules:

   1. 𝑆→𝐴 ∣ 𝐵
   2. 𝐴→𝑎𝐴𝑏 ∣ 𝐶
   3. 𝐵→𝑏𝐵𝑐 ∣ 𝐶
   4. 𝐶→𝜖 (Here, ϵ represents the empty string, accommodating strings where j=0 in either case)

   Explanation of Rules:

   • Rule 1: The start symbol S can derive either A or B. This accounts for the "or" condition in the language definition.
   • Rule 2: A generates strings where the count of a's is equal to b's by adding one a and one b in each step, and can eventually lead to C which terminates the recursion or adjusts for where no further a or b is needed.
   • Rule 3: Similarly, B handles the equal count of b's and c's.
   • Rule 4: C acts as a base case, generating the empty string, which allows A and B to terminate correctly and also handles the case when j=0 (meaning no b's), valid for both A and B.

   This CFG successfully represents the given language by allowing construction of strings where either the counts of 𝑎’s and 𝑏’s are equal or the counts of 𝑏’s and 𝑐’s are equal, satisfying the given condition 𝑖=𝑗 or 𝑗=𝑘.

2. $L = { a^i \ b^j \ c^k \ | \ j>i+k }$

   𝐺=(𝑁,Σ,𝑃,𝑆) where:

   • 𝑁 is the set of nonterminal symbols.
   • Σ is the set of terminal symbols.
   • 𝑃 is the set of production rules.
   • 𝑆 is the start symbol.

   Nonterminal Symbols:

   • 𝑆: Start symbol.
   • 𝑇: Generates strings starting with a central core of extra b's.
   • 𝑋: Generates an a followed by a b, used to balance out a's with some b's.
   • 𝑌: Generates a b followed by a c, used to balance out c's with some b's.

   Terminal Symbols:

   • 𝑎,𝑏,𝑐

   Production Rules:

   1. 𝑆→𝑇𝑏𝑇
   2. 𝑇→𝑋∣𝑌∣𝑋𝑇∣𝑌𝑇∣𝑇∣𝜖
   3. 𝑋→𝑎𝑇𝑏
   4. 𝑌→𝑏𝑇𝑐

   Explanation of Rules:

   • Rule 1: The start symbol S generates a string that begins and ends with additional b's surrounding a middle part generated by T. This ensures that there are more b's than the sum of a's and c's.
   • Rule 2: T can produce X, Y, combinations thereof, or ϵ. This flexibility allows T to generate any number of a's and c's each matched with some b's, plus potentially extra b's.
   • Rule 3: X generates an a followed by some b's, linking the increase of a's to an increase in b's, but still keeping b's ahead.
   • Rule 4: Y generates a b followed by a c, again ensuring b's are added whenever a c is added.

(c) Convert following CFG to CNF : S -> S(S)/^

(7 marks)

To convert a given context-free grammar (CFG) into Chomsky Normal Form (CNF), we need to ensure that all production rules meet the specific criteria of CNF:

1. Binary Productions: Each production rule must either produce exactly two nonterminal symbols or
2. Terminal Productions: A single terminal symbol.

The grammar provided is: 𝑆→𝑆 (𝑆) ∣ 𝜖

Let's convert this CFG into CNF step by step:

Step 1: Eliminate the Empty Production

We start by eliminating the empty production (𝜖) from non-start symbols. If the start symbol 𝑆 can generate 𝜖, we introduce a new start symbol 𝑆0 and add the productions 𝑆0 → 𝑆 ∣ 𝜖. Thus, we modify the grammar:

• 𝑆0 → 𝑆 ∣ 𝜖
• 𝑆 → 𝑆 (𝑆)

Step 2: Eliminate Unit Productions

In this grammar, the only unit production is 𝑆0→𝑆. We eliminate it by replacing it with the productions of 𝑆, resulting in:

• 𝑆0 → 𝑆(𝑆) ∣ 𝜖
• 𝑆 → 𝑆(𝑆)

Step 3: Handle the Terminal Symbols

Since the rule 𝑆→𝑆(𝑆) contains terminals mixed with nonterminals, we introduce new nonterminals for each terminal. Let 𝐴 represent ( and 𝐵 represent ), then add:

• 𝐴→(
• 𝐵→)

Now replace in the original rules:

• 𝑆0→𝑆(𝑆)∣𝜖
• 𝑆→𝑆𝐴𝑆𝐵

Step 4: Eliminate Right-Hand Sides with More Than Two Nonterminals

The production 𝑆→𝑆𝐴𝑆𝐵 has more than two nonterminals. We introduce a new nonterminal 𝑅 to break it down:

• 𝑅→𝐴𝑆
• 𝑆→𝑅𝐵

Now, we have the grammar in Chomsky Normal Form:

1. 𝑆0→𝑅𝐵∣𝜖
2. 𝑆→𝑅𝐵
3. 𝑅→𝐴𝑆
4. 𝐴→(
5. 𝐵→)

This grammar is in CNF and still generates the same language as the original grammar. Each production either leads to exactly two nonterminals or directly to a terminal symbol, and there are no empty productions on non-start symbols or any unit productions.

Q.3

(a) Define Regular grammar and give example. (3 marks)

Regular grammer is a type 3 grammer which accepts regular languages.

FSM i.e (Finite state machine) is used to represent regular grammer.

eg: ab

In regular grammer the languages used are also regular.

eg. a language of all strings that begin with or end with 00 or 11.

Type 3 grammer is called regular grammer.

It is of form : S → tB | t

which says, on the left hand side of grammer there is always a non-terminal & on rhs their is a non-terminal and a terminal or a single terminal.

(b) Explain types of derivation and ambiguity. (4 marks)

Types of derivation

• A grammer can be derived in two ways.

• The two types of derivation are

  1. left most derivation
  2. right most derivation eg. S→aSA | a
     A→ b string is aaabb we will derive this using left-most and right-most derivation. aaabb

  3. Left most derivation

     S

     aSA (S→aSA) aaSAA (S→aSA) aaaAA (S→a) aaabA (A→b) aaabb (A→b)

  4. Right most derivation

     S

     aSA (S→aSA) aSb (A→b) aaSAb (S→aSA) aaSbb (A→b) aaabb (S→a)

Ambiguity

A grammer is said to be ambiguous if for a given grammer more than one parse tree is generated.

eg. S → E+E | E*E | id

(c) Convert following CFG to CNF : S→aX/Yb X→S/^ Y→bY/b

(7 marks) ( e is epsilon)

CFG to CNF

S → aX | Yb

X → S | e

Y → bY | b

1st of all we will remove & productions

X → e

S→aX | Yb | a

X → S Y → bY | b

Now removing unity productions,

S → aX | Yb | a

X → S Y → bY | b

X→S is unit production

After removing it the grammer will be

S → aX | Yb | a

X → aX | Yb | a

Y → bY | b

Here, S=X

therfore, the grammer can also be written as,

S → aS | Yb | a

Y → bY | b

Now converting this grammar into CNF

CNF states for chomsky’s nromal form.

CNF Form is :

NonTerminal → NonTerminal * NonTerminal

NonTermial → Terminal

S → aS S→P1S P→a

S → Yb S→Yp2 p2 → b

S→a is already in normal form.

Y → bY y→ P2Y P2 → b

Y → b already in CNF

Hence,

CNF will be

S→ P1S P1 → a S→YP2 P2→b S→a Y→P2Y P2→b Y→b

Q.4

(a) What is a pushdown automaton? Explain. (3 marks)

Pushdown Automata is a finite automata with extra memory called stack which helps Pushdown automata to recognize Context Free Languages.

A Pushdown Automata (PDA) can be defined as :

• Q is the set of states
• ∑ is the set of input symbols
• Γ is the set of pushdown symbols (which can be pushed and popped from stack)
• q0 is the initial state
• Z is the initial pushdown symbol (which is initially present in stack)
• F is the set of final states
• δ is a transition function which maps Q x {Σ ∪ ∈} x Γ into Q x Γ*. In a given state, PDA will read input symbol and stack symbol (top of the stack) and move to a new state and change the symbol of stack.

(b) Give the difference between top down and bottom up parsing. (4 marks)

Top-Down Parsing	Bottom-Up Parsing
It is a parsing strategy that first looks at the highest level of the parse tree and works down the parse tree by using the rules of grammar.	It is a parsing strategy that first looks at the lowest level of the parse tree and works up the parse tree by using the rules of grammar.
Top-down parsing attempts to find the left most derivations for an input string.	Bottom-up parsing can be defined as an attempt to reduce the input string to the start symbol of a grammar.
In this parsing technique we start parsing from the top (start symbol of parse tree) to down (the leaf node of parse tree) in a top-down manner.	In this parsing technique we start parsing from the bottom (leaf node of the parse tree) to up (the start symbol of the parse tree) in a bottom-up manner.
This parsing technique uses Left Most Derivation.	This parsing technique uses Right Most Derivation.
The main leftmost decision is to select what production rule to use in order to construct the string.	The main decision is to select when to use a production rule to reduce the string to get the starting symbol.
Example: Recursive Descent parser.	Example: ItsShift Reduce parser.

(c) Design and draw deterministic PDA Accepting “Balance string of brackets”. (7 marks)

OR

Q.4

(a) Explain deterministic pushdown automata. (3 marks)

The Deterministic Pushdown Automata is a variation of pushdown automata that accepts the deterministic context-free languages.

A language L(A) is accepted by a deterministic pushdown automata if and only if there is a single computation from the initial configuration until an accepting one for all strings belonging to L(A). It is not as powerful as non-deterministic finite automata. That's why it is less in use and used only where determinism is much easier to implement.

A PDA is said to be deterministic if its transition function δ(q,a,X) has at most one member for -

a ∈ Σ U {ε}

A Deterministic PDA is 5 tuple -

M = (Σ,Γ,Q,δ,q)

Σ - It is a finite set which does not contain a blank symbol, Γ - a finite set of stack alphabet, Q - set of states, q - start state, δ - a transition function, denoted as -

δ : Q × (Σ ∪ {□}) × Γ → Q × {N,R} × Γ∗

(b) Explain conversion from PDA to CFG. (4 marks) (to be checked)

PDA to CFG

let’s take an example :

(q0, 0, z0) = (q0, AZ)

(q0, 0, z0) = (q1, ε )

• (q0,0,z0) = (q0,AZ)
  • FG for this will be [ q0, z0, q0 ] ⇒ 0 [ q0, A, a0 ] [ q0, z, q0 ] [ q0, z0, q0 ] ⇒ 0 [ q0, A, q1 ] [ q1, z, q0 ] [ q0, z0, q1 ] ⇒ 0 [ q0, A, q0 ] [ q0, z, q1 ] [ q0, z0, q1 ] ⇒ 0 [ q0, A, q1 ] [ q1, z, q1 ] -

(c) Design and draw PDA to accept string with more a’s than b’s. (7 marks)

δ(q0,a,z0) = (q0,az0)

δ(q0,b,z0) = (q0,bz0)

δ(q0,a,a) = (q0,aa)

δ(q0,b,b) = (q0,bb)

δ(q0,a,b) = (q0,ε)

δ(q0,b,a) = (q0,ε)

δ(q0,ε,a) = (q1,z0)

PDA = { (q0,q1), (a,b), (a,b,z0), δ, q0, z0, q1 }

The logic is we will simply push all a’s into the stack & on reading each b we will pop one a from the stack, & at the end one a will be there on the top of stack, so we can say there are more a’s than b’s.

example string: aabab

Q.5

(a) What is Turing machine? Explain its capabilities. (3 marks)

A Turing machine is a finite automaton that can read, write, and erase symbols on an infinitely long tape. The tape is divided into squares, and each square contains a symbol. The Turing machine can only read one symbol at a time, and it uses a set of rules (the transition function) to determine its next action based on the current state and the symbol it is reading.

The Turing machine’s behavior is determined by a finite state machine, which consists of a finite set of states, a transition function that defines the actions to be taken based on the current state and the symbol being read, and a set of start and accept states. The Turing machine begins in the start state and performs the actions specified by the transition function until it reaches an accept or reject state. If it reaches an accept state, the computation is considered successful; if it reaches a reject state, the computation is considered unsuccessful.

A TM is expressed as a 7-tuple (Q, T, B, ?, ?, q0, F) where:

• Q is a finite set of states
• T is the tape alphabet (symbols which can be written on Tape)
• B is blank symbol (every cell is filled with B except input alphabet initially)
• ? is the input alphabet (symbols which are part of input alphabet)
• ? is a transition function which maps Q × T ? Q × T × {L,R}. Depending on its present state and present tape alphabet (pointed by head pointer), it will move to new state, change the tape symbol (may or may not) and move head pointer to either left or right.
• q0 is the initial state
• F is the set of final states. If any state of F is reached, input string is accepted.

Capabilities

• the Turing machine can be used to simulate the logic of any computer algorithm
• computation model
• read and write
• Move left right
• Finite state machine
• Decision making
• Halting
• Universality
• Church turing thesis

(b) Explain Church Turing thesis. (4 marks)

Turing machine is defined as an abstract representation of a computing device such as hardware in computers. Alan Turing proposed Logical Computing Machines (LCMs), i.e. Turing’s expressions for Turing Machines. This was done to define algorithms properly. So, Church made a mechanical method named as ‘M’ for manipulation of strings by using logic and mathematics. This method M must pass the following statements:

• Number of instructions in M must be finite.
• Output should be produced after performing finite number of steps.
• It should not be imaginary, i.e. can be made in real life.
• It should not require any complex understanding.

Using these statements Church proposed a hypothesis called

Church’s Turing thesis

that can be stated as: “The assumption that the intuitive notion of computable functions can be identified with partial recursive functions.”

Or in simple words we can say that “Every computation that can be carried out in the real world can be effectively performed by a Turing Machine.”

In 1930, this statement was first formulated by Alonzo Church and is usually referred to as Church’s thesis, or the Church-Turing thesis. However, this hypothesis cannot be proved. The recursive functions can be computable after taking following assumptions:

1. Each and every function must be computable.
2. Let ‘F’ be the computable function and after performing some elementary operations to ‘F’, it will transform a new function ‘G’ then this function ‘G’ automatically becomes the computable function.
3. If any functions that follow above two assumptions must be states as computable function.

(c) Design a Turing machine to copy a string. (7 marks)

Refer [ https://youtu.be/ce2hfGH3ysc?si=CmBF8CmxYXEsP54U ]

OR

Q.5

(a) Explain Primitive Recursive Functions. (3 marks)

(b) Explain Universal Turing machine. (4 marks)

(c) Design a Turing machine to delete a symbol. (7 marks)

Refer [ https://youtu.be/KeB5NdyVHOY?si=JWaE6ZxqNeQaPxy2 ]