2021 105503

B.Tech 5th Semester Exam., 2021

Time 03 Hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Q.1 Choose the correct answer of the following (any seven):

Q1.1

Which of the following statements is/are False?

a)

A. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.

b)

B. Turing recognizable languages are closed under union and complementation.

c)

C. Turing decidable languages are closed under intersection and complementation.

d)

D. Turing recognizable languages are closed under union and intersection.

e)

(i) A and D only (ii) A and C only (iii) B only (iv) C only

Q1.2

Enumerator is a Turing machine with

a)

an output printer

b)

5 input tapes

c)

a stack

d)

None of the above

Q1.3

The language $ \{a^m b^n c^{m+n} \mid m, n \ge 1\} $ is

a)

regular

b)

context-free but not regular

c)

context-sensitive but not context-free

d)

type-0 but not context-sensitive

Q1.4

The maximum number of states of a DFA converted from an NFA with $ n $ states is

a)

$n$

b)

$n^2$

c)

$2^n$

d)

None of the above

Q1.5

If $ L_1 $ and $ L_2 $ are context-free languages, $ L_1 - L_2 $ is

a)

always context-free.

b)

sometimes context-free.

c)

never context-free.

d)

None of the above

Q1.6

Which of the following does not have left recursions?

a)

Chomsky normal form

b)

Greibach normal form

c)

Backus-Naur form

d)

All of the above

Q1.7

Let N be an NFA with $ n $ states and let M be the minimized DFA with $ m $ states recognizing the same language. Which of the following is necessarily true?

a)

$m \le 2^n$

b)

$n \le m$

c)

M has one accept state

d)

$m = 2^n$

Q1.8

_____ is the acyclic graphical representation of a grammar.

a)

Binary tree

b)

Octtree

c)

Parse tree

d)

None of the above

Q1.9

A minimum state deterministic FA accepting the language $ L = \{w \mid w \in \{0, 1\}^*\} $ where number of 0's and 1's in w are divisible by 3 and 5 respectively, has

a)

15 states

b)

11 states

c)

10 states

d)

9 states

Q1.10

The construction time for DFA from an equivalent NFA ($ m $ number of node) is

a)

$O(m^2)$

b)

$O(2^m)$

c)

$O(m)$

d)

$O(\log m)$

Q.2 Solve both questions :

Q2.1

Tabulate Chomsky hierarchy of grammar with an example for each.

Q2.2

Design a finite state machine abstract model for Parity checker.

Q.3 Solve both questions :

Q3.1

Construct an NFA that will accept string of 0's, 1's and 2's beginning with a 0's followed by odd number of 1's and ending with any number of 2's.

Q3.2

Construct a push-down automata that accepts the following language: $ L = \{uawb : u \text{ and } w \in (a,b)^* \text{ and } |u| = |w|\} $

Q.4 Solve both questions :

Q4.1

Design a Turing machine (TM) to compute $ n \mod 2 $.

Q4.2

Design a DFA corresponding to regular expression $ 1^*(10)^* $

Q.5 Solve both questions :

Q5.1

Consider the grammar: $ S \rightarrow AB \mid BC $, $ A \rightarrow BA \mid a $, $ B \rightarrow CC \mid b $, $ C \rightarrow AB \mid a $. Use the CYK algorithm to determine whether the given string "baaba" is in $ L(G) $ or not.

Q5.2

Suppose L is context free and R is regular, justify your answer with the help of example:
(i) Is $ L - R $ necessarily context free?
(ii) Is $ R - L $ necessarily context free?

Q.6 Solve both questions :

Q6.1

Show that the language $ L = \{a^{n!} : n \ge 0\} $ is not regular or not context-free language.

Q6.2

Let G be a context-free grammar in Chomsky normal form that contains $ b $ variable. Show that if G generates some string using a derivation with at least $ 2^b $ steps, then $ L(G) $ is infinite.

Q.7 Solve both questions :

Q7.1

State and prove pumping lemma for regular sets.

Q7.2

Show given grammar over alphabet {a, b}, verify whether it is ambiguous or unambiguous : $ S \rightarrow aSa \mid bSb \mid a \mid b \mid \epsilon $

Q.8 Solve both questions :

Q8.1

Show that the sum function $ f(x, y) = x + y $ is primitive recursive.

Q8.2

Construct a PDA that accepts the language $ L = \{a^{2n}bc \mid n \ge 0\} $ by final state and empty stack.

Q.9 Write short notes on the following:

Q9.1

a)

Post-correspondence problem

b)

Chomsky normal form

c)

Multistack Turing machine

d)

Pumping lemma for CFL

2021 V2 105503

B.Tech 5th Semester Exam., 2021

Time 03 Hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Q.1 Choose the correct answer of the following (any seven):

Q1.1

Which of the following statements is/are False?

a)

A. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.

b)

B. Turing recognizable languages are closed under union and complementation.

c)

C. Turing decidable languages are closed under intersection and complementation.

d)

D. Turing recognizable languages are closed under union and intersection.

e)

(i) A and D only (ii) A and C only (iii) B only (iv) C only

Q1.2

Enumerator is a Turing machine with

a)

an output printer

b)

5 input tapes

c)

a stack

d)

None of the above

Q1.3

The language $\{a^m b^n c^{m+n} \mid m, n \ge 1\}$ is

a)

regular

b)

context-free but not regular

c)

context-sensitive but not context-free

d)

type-0 but not context-sensitive

Q1.4

The maximum number of states of a DFA converted from an NFA with $n$ states is

a)

$n$

b)

$n^2$

c)

$2^n$

d)

None of the above

Q1.5

If $L_1$ and $L_2$ are context-free languages, $L_1 - L_2$ is

a)

always context-free.

b)

sometimes context-free.

c)

never context-free.

d)

None of the above

Q1.6

Which of the following does not have left recursions?

a)

Chomsky normal form

b)

Greibach normal form

c)

Backus-Naur form

d)

All of the above

Q1.7

Let N be an NFA with $n$ states and let M be the minimized DFA with $m$ states recognizing the same language. Which of the following is necessarily true?

a)

$m \le 2^n$

b)

$n \le m$

c)

M has one accept state

d)

$m = 2^n$

Q1.8

_____ is the acyclic graphical representation of a grammar.

a)

Binary tree

b)

Octtree

c)

Parse tree

d)

None of the above

Q1.9

A minimum state deterministic FA accepting the language $ L = {w \mid w \in {0, 1}^*} $ where number of 0's and 1's in w are divisible by 3 and 5 respectively, has

a)

15 states

b)

11 states

c)

10 states

d)

9 states

Q1.10

The construction time for DFA from an equivalent NFA ($ m $ number of node) is

a)

$O(m^2)$

b)

$O(2^m)$

c)

$O(m)$

d)

$O(\log m)$

Q.2 Solve both questions :

Q2.1

Tabulate Chomsky hierarchy of grammar with an example for each.

Q2.2

Design a finite state machine abstract model for Parity checker.

Q.3 Solve both questions :

Q3.1

Construct an NFA that will accept string of 0's, 1's and 2's beginning with a 0's followed by odd number of 1's and ending with any number of 2's.

Q3.2

Construct a push-down automata that accepts the following language: $ L = {uawb : u \text{ and } w \in (a,b)^* \text{ and } |u| = |w|} $

Q.4 Solve both questions :

Q4.1

Design a Turing machine (TM) to compute $n \mod 2$ .

Q4.2

Design a DFA corresponding to regular expression $1^*(10)^*$

Q.5 Solve both questions :

Q5.1

Consider the grammar: $S \rightarrow AB \mid BC$ , $A \rightarrow BA \mid a$ , $ B \rightarrow CC \mid b $,$ C \rightarrow AB \mid a $. Use the CYK algorithm to determine whether the given string "baaba" is in $L(G)$ or not.

Q5.2

Suppose L is context free and R is regular, justify your answer with the help of example:
(i) Is $L - R$ necessarily context free?
(ii) Is $R - L$ necessarily context free?

Q.6 Solve both questions :

Q6.1

Show that the language $L = \{a^{n!} : n \ge 0\}$ is not regular or not context-free language.

Q6.2

Let G be a context-free grammar in Chomsky normal form that contains $b$ variable. Show that if G generates some string using a derivation with at least $2^b$ steps, then $L(G)$ is infinite.

Q.7 Solve both questions :

Q7.1

State and prove pumping lemma for regular sets.

Q7.2

Show given grammar over alphabet {a, b}, verify whether it is ambiguous or unambiguous : $ S \rightarrow aSa \mid bSb \mid a \mid b \mid \epsilon $

Q.8 Solve both questions :

Q8.1

Show that the sum function $f(x, y) = x + y$ is primitive recursive.

Q8.2

Construct a PDA that accepts the language $L = \{a^{2n}bc \mid n \ge 0\}$ by final state and empty stack.

Q.9 Write short notes on the following:

Q9.1

Post-correspondence problem
Chomsky normal form
Multistack Turing machine
Pumping lemma for CFL

a)

Post-correspondence problem

b)

Chomsky normal form

c)

Multistack Turing machine

d)

Pumping lemma for CFL

2020 105503

B.Tech 5th Semester Exam., 2020

Time 03 Hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Q.1 Choose the correct answer of the following (any seven):

Q1.1

Definition of a language L with alphabet {a} is given as $ L = \{a^{nk} \mid k > 0 \}, $ and n is a positive integer constant. What is the minimum number of states needed in a DFA to recognize L?

a)

$k + 1$

b)

$n + 1$

c)

$2^{n+1}$

d)

$2^{k+1}$

Q1.2

Which of the following versions of Unix came up with YACC first?

a)

V3

b)

V5

c)

CB UNIX

d)

UNIX-RT

Q1.3

A pushdown automata can be represented as $ PDA = \epsilon \text{-} NFA + [\text{stack}] $.

a)

True

b)

False

Q1.4

A language accepted by deterministic pushdown automata is closed under which of the following?

a)

Complement

b)

Union

c)

Both (i) and (ii)

d)

None of the above

Q1.5

A _____ is context free grammar with atmost one non-terminal in the right handside of the production.

a)

linear grammar

b)

linear bounded grammar

c)

regular grammar

d)

None of the above

Q1.6

The lexical analysis for a modern language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?

a)

Finite state automata

b)

Deterministic pushdown automata

c)

Non-deterministic pushdown automata

d)

Turing machine

Q1.7

Let $ L = \{w \in (0+1)^* \mid w \text{ has even number of 1s}\} $, i.e., L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?

a)

$(0^*10^*1)^*$

b)

$0^*(10^*10^*)^*$

c)

$0^*(10^*1^*)^*0^*$

d)

$0^*1(10^*1)^*10^*$

Q1.8

What is the minimum number of states in deterministic finite automata (DFA) for string starting with $ ba^2 $ and ending with a over alphabet {a, b}?

a)

Ten

b)

Nine

c)

Eight

d)

None of the above

Q1.9

The decision problem is the function from string to

a)

char

b)

int

c)

boolean

d)

None of the above

Q1.10

A language L may not be accepted by a turing machine if

a)

it is recursively enumerable

b)

it is recursive

c)

L can be enumerated by some turing machine

d)

None of the above

Q.2 Solve both questions :

Q2.1

Write the context-free grammar to create palindrome over {a, b}.

Q2.2

Construct a DFA which accepts the set of all binary strings that interpreted as binary representation of an unsigned decimal integer, is divisible by 5.

Q.3 Solve both questions :

Q3.1

Design a turing machine to compute the sum of two positive integers m and n.

Q3.2

Design a NPDA for accepting the string $ L = $ set of all palindrome over {a, b} by the empty stack and by final state.

Q.4 Solve both questions :

Q4.1

Construct finite automaton corresponding to the regular expression: $ (a+b)^*c d^*e $

Q4.2

Explain the multi-tape version of turing machine and its significance.

Q.5 Solve both questions :

Q5.1

Show given grammar over alphabet {a, b} verify whether it is ambiguous or unambiguous : $ S \rightarrow a / abSb / aAb $, $ A \rightarrow bS / aAAb $

Q5.2

Show that $ L = $ palindrome over {a, b} is not regular.

Q.6 Solve both questions :

Q6.1

Prove that if L is generated by a CFG, then L is accepted by a non-deterministic PDA by empty stack.

Q6.2

Design a pushdown automaton for the following context-free grammar: $ S \rightarrow aB \mid bA $, $ A \rightarrow aS \mid bAA \mid a $, $ B \rightarrow bS \mid aBB \mid b $

Q.7 Solve both questions :

Q7.1

Design a turing machine that accepts all palindromes over $ \Sigma = \{a, b\} $.

Q7.2

Explain Myhill-Nerode theorem for minimization of automata with suitable example.

Q.8 Solve both questions :

Q8.1

Prove that if L is the language generated by an unrestricted grammar $ G=(N,T,P,S) $, then L is recognized by a turing machine.

Q8.2

Design a pushdown automata for accepting the string for the language $ L = \{WW^R \mid W \in (a,b)^*\} $ by the empty stack as well as final state.

Q.9 Write short notes on the following:

Q9.1

a)

Minimization of automata

b)

Type 2 grammar (Context free)

c)

NP-hard problem

d)

Pumping lemma for CFL

2020 V2 105503

B.Tech 5th Semester Exam., 2020

Time 03 Hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Q.1 Choose the correct answer of the following (any seven):

Q1.1

Definition of a language L with alphabet {a} is given as $L = \{a^{nk} \mid k > 0 \},$ and n is a positive integer constant. What is the minimum number of states needed in a DFA to recognize L?

a)

$k + 1$

b)

$n + 1$

c)

$2^{n+1}$

d)

$2^{k+1}$

Q1.2

Which of the following versions of Unix came up with YACC first?

a)

V3

b)

V5

c)

CB UNIX

d)

UNIX-RT

Q1.3

A pushdown automata can be represented as $ PDA = \epsilon \text{-} NFA + [\text{stack}] $.

a)

True

b)

False

Q1.4

A language accepted by deterministic pushdown automata is closed under which of the following?

a)

Complement

b)

Union

c)

Both (i) and (ii)

d)

None of the above

Q1.5

A _____ is context free grammar with atmost one non-terminal in the right handside of the production.

a)

linear grammar

b)

linear bounded grammar

c)

regular grammar

d)

None of the above

Q1.6

The lexical analysis for a modern language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?

a)

Finite state automata

b)

Deterministic pushdown automata

c)

Non-deterministic pushdown automata

d)

Turing machine

Q1.7

Let $L = \{w \in (0+1)^* \mid w \text{ has even number of 1s}\}$ , i.e., L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?

a)

$(0^*10^*1)^*$

b)

$0^*(10^*10^*)^*$

c)

$0^*(10^*1^*)^*0^*$

d)

$0^*1(10^*1)^*10^*$

Q1.8

What is the minimum number of states in deterministic finite automata (DFA) for string starting with $ba^2$ and ending with a over alphabet {a, b}?

a)

Ten

b)

Nine

c)

Eight

d)

None of the above

Q1.9

The decision problem is the function from string to

a)

char

b)

int

c)

boolean

d)

None of the above

Q1.10

A language L may not be accepted by a turing machine if

a)

it is recursively enumerable

b)

it is recursive

c)

L can be enumerated by some turing machine

d)

None of the above

Q.2 Solve both questions :

Q2.1

Write the context-free grammar to create palindrome over {a, b}.

Q2.2

Construct a DFA which accepts the set of all binary strings that interpreted as binary representation of an unsigned decimal integer, is divisible by 5.

Q.3 Solve both questions :

Q3.1

Design a turing machine to compute the sum of two positive integers m and n.

Q3.2

Design a NPDA for accepting the string $L =$ set of all palindrome over {a, b} by the empty stack and by final state.

Q.4 Solve both questions :

Q4.1

Construct finite automaton corresponding to the regular expression: $(a+b)^*c d^*e$

Q4.2

Explain the multi-tape version of turing machine and its significance.

Q.5 Solve both questions :

Q5.1

Show given grammar over alphabet {a, b} verify whether it is ambiguous or unambiguous : $ S \rightarrow a / abSb / aAb $,$ A \rightarrow bS / aAAb $

Q5.2

Show that $L =$ palindrome over {a, b} is not regular.

Q.6 Solve both questions :

Q6.1

Prove that if L is generated by a CFG, then L is accepted by a non-deterministic PDA by empty stack.

Q6.2

Design a pushdown automaton for the following context-free grammar: $ S \rightarrow aB \mid bA $, $A \rightarrow aS \mid bAA \mid a$ , $B \rightarrow bS \mid aBB \mid b$

Q.7 Solve both questions :

Q7.1

Design a turing machine that accepts all palindromes over $\Sigma = \{a, b\}$ .

Q7.2

Explain Myhill-Nerode theorem for minimization of automata with suitable example.

Q.8 Solve both questions :

Q8.1

Prove that if L is the language generated by an unrestricted grammar $G=(N,T,P,S)$ , then L is recognized by a turing machine.

Q8.2

Design a pushdown automata for accepting the string for the language $ L = {WW^R \mid W \in (a,b)^*} $ by the empty stack as well as final state.

Q.9 Write short notes on the following:

Q9.1

Minimization of automata
Type 2 grammar (Context free)
NP-hard problem
Pumping lemma for CFL

a)

Minimization of automata

b)

Type 2 grammar (Context free)

c)

NP-hard problem

d)

Pumping lemma for CFL

2019 051611

B.Tech 6th Semester Exam., 2019

Time 03 Hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Q.1 Choose the correct answer/Fill in the blank of any seven of the following:

Q1.1

The word 'formal' in formal languages means

a)

they are unnecessary, in reality

b)

the symbols used have well-defined meaning

c)

only the form of the string of symbols is significant

d)

None of the above

Q1.2

Which of the following statements is true?

a)

If a language is context-free, it can always be accepted by a deterministic push-down automaton.

b)

The union of two context-free languages is context-free.

c)

The intersection of two context-free languages is context-free.

d)

The complement of a context-free language is context-free.

Q1.3

Which of the following pairs of regular expressions are equivalent?

a)

$x^*$ and $x^*x$

b)

$1(01)^*$ and $(10)^*1$

c)

$x(xx)^*$ and $(xx)^*x$

d)

All of the above

Q1.4

Which of the following pairs have DIFFERENT expressive powers?

a)

Deterministic finite automata (DFA) and non-deterministic finite automata (NDFA)

b)

Deterministic push-down automata (DPDA) and non-deterministic push-down automata (NDPDA)

c)

Deterministic single-tape Turing machine and non-deterministic single-tape Turing machine

d)

Single-tape Turing machine and multi-tape Turing machine

Q1.5

Definition of a language L with alphabet {a} is given as $ L = \{a^{nk} \mid k > 0 \text{ and n is a positive integer constant}\} $. What is the minimum number of states needed in a DFA to recognize L?

a)

$k + 1$

b)

$n + 1$

c)

$2n + 1$

d)

$2k + 1$

Q1.6

Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP complete (NPC)?

a)

(A) P and NP are disjoint

b)

(B) P and NP overlap, with NPC in intersection

c)

(C) P = NP = NPC

d)

(D) P != NP, NPC inside NP

Q1.7

Let L1 be a recursive language. Let L2 and L3 be languages that are not recursively enumerable but recursive. Which of the following statements is not necessarily true?

a)

L2-L1 is recursively enumerable.

b)

L1-L3 is recursively enumerable.

c)

L2 ∩ L1 is recursively enumerable.

d)

L2 ∪ L1 is recursively enumerable.

Q1.8

A PDM behaves like an FSM when the number of auxiliary memory it has, is

a)

0

b)

1

c)

2

d)

None of the above

Q1.9

Define Turing machine in brief.

Q1.10

A finite automaton with _____ is equivalent to push-down automata.

Q.2 Solve this question :

Q2.1

Consider the set of strings on {0, 1} defined by the requirements below. For each, construct an accepting dfa:
(i) Every 00 is followed immediately by a 1. For example, the strings 101, 0010, 001001 are in the language, but 0001 and 00100 are not.
(ii) All strings containing 00 but not 000.
(iii) The leftmost symbol differs from the rightmost one.
(iv) Every substring of four symbols has at most two 0's. For example, 001110 and 011001 are in the language, but 10010 is not since one of its substrings, 0010, contains three zeros.

Q.3 Solve both questions :

Q3.1

Construct the regular grammar accepting the following language: $ L = w \in \{a, b\}^* \mid w \text{ is a string over } \{a, b\} $ $ \text{ such that the number of b's is } 3 \mod 4 $

Q3.2

Let $ G = (V, T, S, P) $ be a right-linear grammar. Prove that the language generated using the grammar G is a regular.

Q.4 Solve both questions :

Q4.1

Construct a Moore machine equivalent to the Mealy machine M defined by the following Table 1 state transitions:

Present State	a = 0		a = 1
Present State	Next State	Output	Next State	Output
$ q_1 $	$ q_1 $	1	$ q_2 $	0
$ q_2 $	$ q_4 $	1	$ q_4 $	1
$ q_3 $	$ q_2 $	1	$ q_3 $	1
$ q_4 $	$ q_3 $	0	$ q_1 $	1

Q4.2

Prove the following equation : $ (1+00^*1) + (1+00^*1)(0+10^*1)^*(0+10^*1) $ = $ 0^*1(0+10^*1)^* $

Q.5 Solve this question :

Q5.1

Using the pumping lemma theorem, show that the following sets are not regular:

$ L = \{a^n b^l a^k : k \ge n+l\} $

$ L = \{w : n_a(w) = n_b(w)\} $

$ L = \{ww w^R : w \in \{a,b\}^*\} $

Q.6 Solve both questions :

Q6.1

Convert the grammar into Chomsky normal form: $ S \rightarrow aB \mid AB $, $ A \rightarrow aab \mid \lambda $, $ B \rightarrow bbA $

Q6.2

Show that the family of unambiguous context-free languages is not closed under union.

Q.7 Solve this question :

Q7.1

Construct an npda corresponding to the grammar: $ S \rightarrow aABB \mid aAA $, $ A \rightarrow aBB \mid a $, $ B \rightarrow bBB \mid A $

Q.8 Solve this question :

Q8.1

Construct Turing machines that will accept the following languages on {a, b}:

$ L = \{w : n_a(w) = n_b(w)\} $

$ L = \{wcw : w \in \{a,b\}^*\} $

Q.9 Solve both questions :

Q9.1

Design a Turing machine with no more than three states that accepts the language $ L(a(a+b)^*) $. Assume that $ \Sigma = \{a, b\} $. Is it possible to do this with a two-state machine?

Q9.2

Let G be an undirected graph. An Euler circuit of the graph is a simple cycle that includes all edges. The Euler Circuit Problem (EULER) is to decide if G has an Euler circuit. Show that EULER is not NP-complete.

2019 V4 051611

B.Tech 6th Semester Exam., 2019

Time 03 Hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Q.1 Choose the correct answer/Fill in the blank of any seven of the following:

Q1.1

The word 'formal' in formal languages means

a)

they are unnecessary, in reality

b)

the symbols used have well-defined meaning

c)

only the form of the string of symbols is significant

d)

None of the above

Q1.2

Which of the following statements is true?

a)

If a language is context-free, it can always be accepted by a deterministic push-down automaton.

b)

The union of two context-free languages is context-free.

c)

The intersection of two context-free languages is context-free.

d)

The complement of a context-free language is context-free.

Q1.3

Which of the following pairs of regular expressions are equivalent?

a)

$x^*$ and $x^*x$

b)

$1(01)^*$ and $(10)^*1$

c)

$x(xx)^*$ and $(xx)^*x$

d)

All of the above

Q1.4

Which of the following pairs have DIFFERENT expressive powers?

a)

Deterministic finite automata (DFA) and non-deterministic finite automata (NDFA)

b)

Deterministic push-down automata (DPDA) and non-deterministic push-down automata (NDPDA)

c)

Deterministic single-tape Turing machine and non-deterministic single-tape Turing machine

d)

Single-tape Turing machine and multi-tape Turing machine

Q1.5

Definition of a language L with alphabet {a} is given as $ L = \{a^{nk} \mid k > 0 \text{ and n is a positive integer constant}\} $. What is the minimum number of states needed in a DFA to recognize L?

a)

$k + 1$

b)

$n + 1$

c)

$2n + 1$

d)

$2k + 1$

Q1.6

Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP complete (NPC)?

a)

(A) P and NP are disjoint

b)

(B) P and NP overlap, with NPC in intersection

c)

(C) P = NP = NPC

d)

(D) P != NP, NPC inside NP

Q1.7

Let L1 be a recursive language. Let L2 and L3 be languages that are not recursively enumerable but recursive. Which of the following statements is not necessarily true?

a)

L2-L1 is recursively enumerable.

b)

L1-L3 is recursively enumerable.

c)

L2 ∩ L1 is recursively enumerable.

d)

L2 ∪ L1 is recursively enumerable.

Q1.8

A PDM behaves like an FSM when the number of auxiliary memory it has, is

a)

0

b)

1

c)

2

d)

None of the above

Q1.9

Define Turing machine in brief.

Q1.10

A finite automaton with _____ is equivalent to push-down automata.

Q.2 Solve this question :

Q2.1

Consider the set of strings on {0, 1} defined by the requirements below. For each, construct an accepting dfa:
(i) Every 00 is followed immediately by a 1. For example, the strings 101, 0010, 001001 are in the language, but 0001 and 00100 are not.
(ii) All strings containing 00 but not 000.
(iii) The leftmost symbol differs from the rightmost one.
(iv) Every substring of four symbols has at most two 0's. For example, 001110 and 011001 are in the language, but 10010 is not since one of its substrings, 0010, contains three zeros.

Q.3 Solve both questions :

Q3.1

Construct the regular grammar accepting the following language: $ L = w \in \{a, b\}^* \mid w \text{ is a string over } \{a, b\} $ $ \text{ such that the number of b's is } 3 \mod 4 $

Q3.2

Let $ G = (V, T, S, P) $ be a right-linear grammar. Prove that the language generated using the grammar G is a regular.

Q.4 Solve both questions :

Q4.1

Construct a Moore machine equivalent to the Mealy machine M defined by the following Table 1 state transitions:

Present State	a = 0		a = 1
Present State	Next State	Output	Next State	Output
$ q_1 $	$ q_1 $	1	$ q_2 $	0
$ q_2 $	$ q_4 $	1	$ q_4 $	1
$ q_3 $	$ q_2 $	1	$ q_3 $	1
$ q_4 $	$ q_3 $	0	$ q_1 $	1

Q4.2

Prove the following equation : $ (1+00^*1) + (1+00^*1)(0+10^*1)^*(0+10^*1) $ = $ 0^*1(0+10^*1)^* $

Q.5 Solve this question :

Q5.1

Using the pumping lemma theorem, show that the following sets are not regular:

$ L = \{a^n b^l a^k : k \ge n+l\} $

$ L = \{w : n_a(w) = n_b(w)\} $

$ L = \{ww w^R : w \in \{a,b\}^*\} $

Q.6 Solve both questions :

Q6.1

Convert the grammar into Chomsky normal form: $ S \rightarrow aB \mid AB $, $ A \rightarrow aab \mid \lambda $, $ B \rightarrow bbA $

Q6.2

Show that the family of unambiguous context-free languages is not closed under union.

Q.7 Solve this question :

Q7.1

Construct an npda corresponding to the grammar: $ S \rightarrow aABB \mid aAA $, $ A \rightarrow aBB \mid a $, $ B \rightarrow bBB \mid A $

Q.8 Solve this question :

Q8.1

Construct Turing machines that will accept the following languages on {a, b}:

$ L = \{w : n_a(w) = n_b(w)\} $

$ L = \{wcw : w \in \{a,b\}^*\} $

Q.9 Solve both questions :

Q9.1

Design a Turing machine with no more than three states that accepts the language $ L(a(a+b)^*) $. Assume that $ \Sigma = \{a, b\} $. Is it possible to do this with a two-state machine?

Q9.2

Let G be an undirected graph. An Euler circuit of the graph is a simple cycle that includes all edges. The Euler Circuit Problem (EULER) is to decide if G has an Euler circuit. Show that EULER is not NP-complete.

2018 051611

B.Tech 6th Semester Exam., 2018

Time 03 Hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Q.1 Choose the correct answer for any seven of the following:

Q1.1

Regular expressions are closed under

a)

union

b)

intersection

c)

Kleene star

d)

All of the above

Q1.2

Extended transition function is

a)

$Q \times \Sigma^* \rightarrow Q$

b)

$Q \times \Sigma^* \rightarrow \Sigma$

c)

$Q \times \Sigma \rightarrow Q$

d)

$Q \times \Sigma \rightarrow \Sigma$

Q1.3

From the options given below, the pair having different expressive powers is

a)

deterministic pushdown automata (DPDA) and non-deterministic pushdown automata (NPDA)

b)

deterministic finite automata (DFA) and non-deterministic finite automata (NFA)

c)

single-tape turing machine and multi-tape turing machine

d)

deterministic single-tape turing machine and non-deterministic single-tape turing machine

Q1.4

For the language $ \{a^p \mid p \text{ is a prime}\} $, the statement which holds true is

a)

it is not regular but context-free

b)

it is regular but not context-free

c)

it is neither regular nor context-free, but accepted by a turing machine

d)

it is not accepted by turing machine

Q1.5

Which one of the following statements is true?

a)

The intersection of two context-free languages is context-free.

b)

A context-free language can always be accepted by a deterministic push-down automaton.

c)

The union of two context-free languages is context-free.

d)

The complement of a context-free language is context-free.

Q1.6

A class of language that is closed under

a)

union and complementation has to be closed under intersection

b)

intersection and complement has to be closed under union

c)

union and intersection has to be closed under complementation

d)

Both (i) and (ii)

Q1.7

CFG can be recognized by

a)

a push-down automaton

b)

a 2-way linear bounded automaton

c)

Both (i) and (ii)

d)

None of the above

Q1.8

A given grammar is called ambiguous, if

a)

two or more productions have the same non-terminal on the left-hand side

b)

a derivation tree has more than one associated sentence

c)

there is a sentence with more than one derivation tree corresponding to it

d)

brackets are not present in the grammar

Q1.9

The output of the Mealy machine depends

a)

only on present state

b)

only on current input symbol

c)

both on present state and current input symbol

d)

None of the above

Q1.10

The logic of pumping lemma is a good example of

a)

pigeon-hole principle

b)

divide-and-conquer technique

c)

recursion

d)

iteration

Q.2 Solve both questions :

Q2.1

For each of the following languages, construct a DFA that accepts the language. In all cases, the alphabet is {0, 1}:
(i) {w : the length of w is divisible by three}
(ii) {w : 110 is not a substring of w}
(iii) {w : w contains at least five 1's}
(iv) {w : w contains the substring 1011}
(v) {w : w contains at least two 1's and at most two 0's}

Q2.2

State and proof pumping lemma for regular languages.

Q.3 Solve both questions :

Q3.1

Using pumping lemma, show that the language $ A = \{ww \mid w \in \{0, 1\}^*\} $ is not regular.

Q3.2

Let A be a non-empty regular language. Prove that there exists an NFA that accepts A and that has exactly one accept state.

Q3.3

Convert each of the following regular expressions to an NFA: (i) $ (0 \cup 1) 1^* 000 (0 \cup 1)^* $ (ii) $ (((10)^*(001) \cup 10))^* $ (iii) $ (baa + abb)^* $

Q.4 Solve this question :

Q4.1

(a) Prove the following two properties: (i) Regular sets are closed over the intersection operation. (ii) Regular sets are closed over the union operation.
(b) Represent the language that contains strings over $ \Sigma = \{0, 1\} $ and has even number of 0's.
(c) Convert the following DFA to a regular expression:

Q.5 Solve this question :

Q5.1

(a) Construct context-free grammars that generate the following languages. In all cases $ \Sigma = \{a, b\} $: (i) $ a^*b $ (ii) $ (ab)^* $
(b) Construct a CFG for the set of non-negative odd integers.

Q.6 Solve both questions :

Q6.1

Let A and B be context-free languages over the same alphabet $ \Sigma $.
(i) Prove that the union $ A \cup B $ of A and B is also context-free.
(ii) Prove that the concatenation AB of A and B is also context-free.
(iii) Prove that the star $ A^* $ of A is also context-free.

Q6.2

Determine a CFG without unit production equivalent to the CFG given below: $ S \rightarrow a \mid Xb \mid aYa \mid b \mid aa $, $ X \rightarrow Y $, $ Y \rightarrow b \mid X $

Q.7 Solve this question :

Q7.1

(a) Find the CNF (Chomsky Normal Form) for the following CFG: $ S \rightarrow ABA $, $ A \rightarrow aA \mid \epsilon $, $ B \rightarrow bB \mid \epsilon $
(b) Eliminate null productions from the following CFG: $ S \rightarrow Xa $, $ X \rightarrow aX \mid bX \mid \epsilon $
(c) Convert the following grammar to GNF: $ A_1 \rightarrow A_2 A_3 $, $ A_2 \rightarrow A_3 A_1 \mid b $, $ A_3 \rightarrow A_1 A_2 \mid a $

Q.8 Solve both questions :

Q8.1

Construct npda that accepts the following languages on $ \Sigma = \{a, b, c\} $:
(i) $ L = \{a^n b^{2n} : n \ge 0\} $
(ii) $ L = \{wcw^R : w \in \{a,b\}^*\} $
(iii) $ L = \{w : n_a(w) = 2n_b(w)\} $

Q8.2

Design a PDA that accepts the language $ L = \{a^n b^m a^n : m, n > 0\} $

Q.9 Solve this question :

Q9.1

(a) Design a Turing machine that recognizes strings containing equal number of 0's and 1's.
(b) Let $ L_1 $ be recursive and $ L_2 $ recursively enumerable. Show that $ L_2 - L_1 $ is necessarily recursively enumerable.
(c) Define P, NP, NPH and NPC problems with example.

2018 V4 051611

B.Tech 6th Semester Exam., 2018

Time 03 Hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Q.1 Choose the correct answer for any seven of the following:

Q1.1

Regular expressions are closed under

a)

union

b)

intersection

c)

Kleene star

d)

All of the above

Q1.2

Extended transition function is

a)

$Q \times \Sigma^* \rightarrow Q$

b)

$Q \times \Sigma^* \rightarrow \Sigma$

c)

$Q \times \Sigma \rightarrow Q$

d)

$Q \times \Sigma \rightarrow \Sigma$

Q1.3

From the options given below, the pair having different expressive powers is

a)

deterministic pushdown automata (DPDA) and non-deterministic pushdown automata (NPDA)

b)

deterministic finite automata (DFA) and non-deterministic finite automata (NFA)

c)

single-tape turing machine and multi-tape turing machine

d)

deterministic single-tape turing machine and non-deterministic single-tape turing machine

Q1.4

For the language $ \{a^p \mid p \text{ is a prime}\} $, the statement which holds true is

a)

it is not regular but context-free

b)

it is regular but not context-free

c)

it is neither regular nor context-free, but accepted by a turing machine

d)

it is not accepted by turing machine

Q1.5

Which one of the following statements is true?

a)

The intersection of two context-free languages is context-free.

b)

A context-free language can always be accepted by a deterministic push-down automaton.

c)

The union of two context-free languages is context-free.

d)

The complement of a context-free language is context-free.

Q1.6

A class of language that is closed under

a)

union and complementation has to be closed under intersection

b)

intersection and complement has to be closed under union

c)

union and intersection has to be closed under complementation

d)

Both (i) and (ii)

Q1.7

CFG can be recognized by

a)

a push-down automaton

b)

a 2-way linear bounded automaton

c)

Both (i) and (ii)

d)

None of the above

Q1.8

A given grammar is called ambiguous, if

a)

two or more productions have the same non-terminal on the left-hand side

b)

a derivation tree has more than one associated sentence

c)

there is a sentence with more than one derivation tree corresponding to it

d)

brackets are not present in the grammar

Q1.9

The output of the Mealy machine depends

a)

only on present state

b)

only on current input symbol

c)

both on present state and current input symbol

d)

None of the above

Q1.10

The logic of pumping lemma is a good example of

a)

pigeon-hole principle

b)

divide-and-conquer technique

c)

recursion

d)

iteration

Q.2 Solve both questions :

Q2.1

For each of the following languages, construct a DFA that accepts the language. In all cases, the alphabet is {0, 1}:
(i) {w : the length of w is divisible by three}
(ii) {w : 110 is not a substring of w}
(iii) {w : w contains at least five 1's}
(iv) {w : w contains the substring 1011}
(v) {w : w contains at least two 1's and at most two 0's}

Q2.2

State and proof pumping lemma for regular languages.

Q.3 Solve both questions :

Q3.1

Using pumping lemma, show that the language $ A = \{ww \mid w \in \{0, 1\}^*\} $ is not regular.

Q3.2

Let A be a non-empty regular language. Prove that there exists an NFA that accepts A and that has exactly one accept state.

Q3.3

Convert each of the following regular expressions to an NFA: (i) $ (0 \cup 1) 1^* 000 (0 \cup 1)^* $ (ii) $ (((10)^*(001) \cup 10))^* $ (iii) $ (baa + abb)^* $

Q.4 Solve this question :

Q4.1

(a) Prove the following two properties: (i) Regular sets are closed over the intersection operation. (ii) Regular sets are closed over the union operation.
(b) Represent the language that contains strings over $ \Sigma = \{0, 1\} $ and has even number of 0's.
(c) Convert the following DFA to a regular expression:

Q.5 Solve this question :

Q5.1

(a) Construct context-free grammars that generate the following languages. In all cases $ \Sigma = \{a, b\} $: (i) $ a^*b $ (ii) $ (ab)^* $
(b) Construct a CFG for the set of non-negative odd integers.

Q.6 Solve both questions :

Q6.1

Let A and B be context-free languages over the same alphabet $ \Sigma $.
(i) Prove that the union $ A \cup B $ of A and B is also context-free.
(ii) Prove that the concatenation AB of A and B is also context-free.
(iii) Prove that the star $ A^* $ of A is also context-free.

Q6.2

Determine a CFG without unit production equivalent to the CFG given below: $ S \rightarrow a \mid Xb \mid aYa \mid b \mid aa $, $ X \rightarrow Y $, $ Y \rightarrow b \mid X $

Q.7 Solve this question :

Q7.1

(a) Find the CNF (Chomsky Normal Form) for the following CFG: $ S \rightarrow ABA $, $ A \rightarrow aA \mid \epsilon $, $ B \rightarrow bB \mid \epsilon $
(b) Eliminate null productions from the following CFG: $ S \rightarrow Xa $, $ X \rightarrow aX \mid bX \mid \epsilon $
(c) Convert the following grammar to GNF: $ A_1 \rightarrow A_2 A_3 $, $ A_2 \rightarrow A_3 A_1 \mid b $, $ A_3 \rightarrow A_1 A_2 \mid a $

Q.8 Solve both questions :

Q8.1

Construct npda that accepts the following languages on $ \Sigma = \{a, b, c\} $:
(i) $ L = \{a^n b^{2n} : n \ge 0\} $
(ii) $ L = \{wcw^R : w \in \{a,b\}^*\} $
(iii) $ L = \{w : n_a(w) = 2n_b(w)\} $

Q8.2

Design a PDA that accepts the language $ L = \{a^n b^m a^n : m, n > 0\} $

Q.9 Solve this question :

Q9.1

(a) Design a Turing machine that recognizes strings containing equal number of 0's and 1's.
(b) Let $ L_1 $ be recursive and $ L_2 $ recursively enumerable. Show that $ L_2 - L_1 $ is necessarily recursively enumerable.
(c) Define P, NP, NPH and NPC problems with example.

2017 051611

B.Tech Examination, 2017

Time 3 hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Questions

Q1

Choose the correct alternatives for any seven of the following :

a)

The output of the Moore Machine depends (a) only on present state (b) only on current input symbol (c) both on present state and current input symbol (d) none of the above

b)

The logic of Pumping lemma is a good example of (a) the pigeon-hole principle (b) the divide and conquer technique (c) recursion (d) iteration

c)

Recursively enumerable languages are not closed under (a) union (b) intersection (c) complementation (d) concatenation

d)

The language $L = \{a^n b^n a^n, \text{where } n = 1, 2, 3, \dots\}$ is a (a) regular language (b) context-free language (c) non-context-free (d) none of the above

e)

A language $L$ is denoted by a regular expression $L = (x)^* (x | yx^*)$ . Which of the following is not a legal string within $L$ ? (a) $x$ (b) $xyxyx$ (c) $xyx$ (d) none of the above

f)

Context free languages are not closed under (a) union (b) intersection (c) concatenation

g)

Recursive languages are (a) a proper superset of CFLs. (b) Always recognizable (c) Also called type 0 languages (d) Recognizable by Turing Machines

h)

Choose the incorrect statements (a) Every subset of a countable set is countable (b) The class of DPDA is not countable (c) the class of TMs is countable (d) the class of LBA is countable

i)

Which of the following statements is true? (a) The language $\{a^n \mid n \text{ is prime}\}$ is regular language (b) The union of 2 recursive languages is Recursive. (c) Recursive enumerable languages are closed under complementation. (d) Recursive languages are not closed under complementation

j)

In case of TM, by reading input $x$ , TM (a) may go to halt-final state (b) may go to halt-non final state (c) may go to infinite loop (d) All of the above

[14 Marks]

Q2

Answer the following:

a)

Obtain the regular expression for the following sets :

[12 Marks]

b)

Describe in simple English the language represented by the regular expression $r = (1+10)^*$ .

[2 Marks]

Q3

Answer the following:

a)

Construct NFA equivalent to the following Regular expression : $10(0 | 1)0^* 1$ .

[4 Marks]

b)

Construct an NFA with $\epsilon$ moves for the regular expression $r = (a^* + b^*)$ .

[5 Marks]

c)

Construct NFA for the Set of all strings over $\Sigma = \{0, 1\}$ with alternate 0's and 1's.

[5 Marks]

Q4

Answer the following:

a)

Construct a DFA for the regular expression $r = (a | b)^* aa(ab | ba)$ .

[7 Marks]

b)

Find out the regular expression for the following FA : [Table required]

[7 Marks]

Q5

Answer the following:

a)

Prove the following two properties : (i) Regular sets are closed over the union operation (ii) Regular sets are closed over the intersection operation

[6 Marks]

b)

Show with the help of pumping lemma that following languages are not regular :

[8 Marks]

Q6

Answer the following:

a)

Give the CFG for each of the languages defined by the following regular expressions :

[9 Marks]

b)

Construct a CFG for the following language set : $L = \{ a^n b^n \mid n \geq 1 \}$ .

[5 Marks]

Q7

Answer the following:

a)

For the grammar $G$ , which is defined as $S \rightarrow aB \mid bA$ $A \rightarrow a \mid aS \mid bAA$ $B \rightarrow b \mid bS \mid aBB$ where $S$ is the starting symbol, show the leftmost derivation, rightmost derivation and parse tree for the string 'bbaaba'.

[9 Marks]

b)

Determine a CFG without unit production equivalent to the CFG given below : $S \rightarrow Abb$ $A \rightarrow Bb$ $B \rightarrow Sa$

[5 Marks]

Q8

Answer the following:

a)

Find the CNF (Chomsky Normal Form) for the following CFG : $S \rightarrow aSa \mid bSb \mid a \mid b \mid aa \mid bb$

[5 Marks]

b)

Eliminate null productions from the following CFG : $A \rightarrow aBb \mid bBa$ $B \rightarrow abB \mid bB \mid \epsilon$

[4 Marks]

c)

Convert the following grammar to GNF : $S \rightarrow ABA \mid AB \mid BA \mid AA \mid A \mid B$ $A \rightarrow aA \mid a$ $B \rightarrow bB \mid b$

[5 Marks]

Q9

Answer the following:

a)

Design a PDA that accepts all palindrome strings over $\Sigma = \{a, b\}$ .

[5 Marks]

b)

Design a PDA that accepts the language $L = \{ a^{2n} \mid n > 0 \}$ .

[5 Marks]

c)

Show that $L = \{ a^p \mid p \text{ is prime} \}$ is not a context-free language.

[4 Marks]

2016 051611

B.Tech Examination, 2016

Time 3 hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Questions

Q1

Choose the correct answer for any seven of the following :

a)

The output of the Moore Machine depends (i) only on present state (ii) only on current input symbol (iii) both on present state and current input symbol (iv) None of the above

b)

The logic of pumping lemma is a good example of (i) the pigeon-hole principle (ii) the divide-and-conquer technique (iii) recursion (iv) iteration

c)

Regular languages are closed under (i) union (ii) intersection (iii) complementation (iv) All of the above

d)

The language $L = \{a^n b^n a^n, \text{where } n = 1, 2, 3, \dots\}$ is a (i) regular language (ii) context-free language (iii) non context-free language (iv) None of the above

e)

A language $L$ is denoted by a regular expression $L = (ab | ba) abb$ . Which of the following is not a legal string within $L$ ? (i) $ababb$ (ii) $abbaabb$ (iii) $baabb$ (iv) None of the above

f)

Context-free languages are not closed under (i) union (ii) intersection (iii) concatenation

g)

Context-free languages are (i) a proper superset of regular languages (ii) recognizable by PDA (iii) also called type 2 languages (iv) All of the above

h)

Choose the incorrect statements : (i) Every subset of a countable set is countable (ii) The class of DPDA is not countable (iii) The class of TMs is countable (iv) The class of LBA is countable

i)

Which of the following statements is true? (i) The language $\{a^n \mid n \text{ is prime}\}$ is regular language. (ii) The union of 2 recursive languages is recursive. (iii) Recursive enumerable languages are closed under complementation. (iv) Recursive languages are not closed under complementation.

j)

In case of TM, in which of the following cases a string will be accepted? (i) Entire string has been consumed and TM halts in the final state (ii) Entire string has been consumed and TM halts is the non-final state (iii) Entire string has not been consumed and TM halts is in any state

[14 Marks]

Q2

Answer the following:

a)

Obtain the regular expression for the following sets :

[10 Marks]

b)

Show that $(ab)^* \neq a^* b^*$ .

[4 Marks]

Q3

Answer the following:

a)

Construct NFA equivalent to the following regular expression : $r = (ab | ba)^* aa(ab | ba)^*$ .

[4 Marks]

b)

Construct an NFA with $\epsilon$ moves for the regular expression $r = a(a+b)^*$ .

[5 Marks]

c)

Construct an NFA for the set of all strings over $\Sigma = \{a, b\}$ with exactly two $a$ .

[5 Marks]

Q4

Answer the following:

a)

Construct a DFA for the regular expression $r = 0^* 1^* 2^*$ .

[7 Marks]

b)

Find out the regular expression for the following transition diagram : [Diagram required]

[7 Marks]

Q5

Answer the following:

a)

Prove the following two properties : (i) Regular sets are closed over the concatenation operation (ii) Regular sets are closed over the complement operation.

[6 Marks]

b)

Show with the help of pumping lemma that following language is not regular : $L = \{ ww \mid w \in \{0, 1\}^* \}$ .

[4 Marks]

c)

Represent the language that contains strings over $\Sigma = \{0, 1\}$ and has even number of 0's.

[4 Marks]

Q6

Answer the following:

a)

Give the CFG for each of the languages defined by the following regular expressions :

[9 Marks]

b)

Construct a CFG for the set of non-negative odd integers.

[5 Marks]

Q7

Answer the following:

a)

For the grammar $G$ , which is defined as $S \rightarrow aB \mid bA$ $A \rightarrow a \mid aS \mid bAA$ $B \rightarrow b \mid bS \mid aBB$ where $S$ is the starting symbol, show the leftmost derivation, rightmost derivation and parse tree for the string 'abbbaa'.

[9 Marks]

b)

Determine a CFG without unit production equivalent to the CFG given below : $S \rightarrow a \mid Xb \mid aYa \mid b \mid aa$ $X \rightarrow Y$ $Y \rightarrow b \mid X$

[5 Marks]

Q8

Answer the following:

a)

Find the CNF (Chomsky Normal Form) for the following CFG : $S \rightarrow ABA$ $A \rightarrow aaA \mid \epsilon$ $B \rightarrow bB \mid \epsilon$

[5 Marks]

b)

Eliminate null productions from the following CFG : $S \rightarrow Xa$ $X \rightarrow aX \mid bX \mid \epsilon$

[4 Marks]

c)

Convert the following grammar to GNF : $A_1 \rightarrow A_2 A_3$ $A_2 \rightarrow A_3 A_1 \mid b$ $A_3 \rightarrow A_1 A_2 \mid a$

[5 Marks]

Q9

Answer the following:

a)

Design a PDA that accepts the language $L = \{ wcw^R \mid w \in \{0, 1\}^* \}$ .

[4 Marks]

b)

Design a PDA that accepts the language $L = \{ a^n b^m a^n \mid m, n > 0 \}$ .

[4 Marks]

c)

Design a TM that recognizes strings containing equal number of 0's and 1's.

[6 Marks]

2015 051611

B.Tech Examination, 2015

Time 3 hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Questions

Q1

Define any seven of the following :

a)

Applications of automata theory

b)

Finite automata

c)

Transition graph

d)

Epsilon transition

e)

Regular expression

f)

Regular language

g)

Turing acceptable

h)

Mealy machine

i)

Reducibility

j)

Enumerable language

[14 Marks]

Q2

Answer the following:

a)

Design an FA that accepts set of strings containing exactly four 1's in every string over alphabets $\Sigma = \{0, 1\}$ .

[7 Marks]

b)

Design an NFA for the language $L = \text{all strings over } \{0, 1\} \text{ that have at least two consecutive 0's or 1's}$ .

[7 Marks]

Q3

Answer the following:

a)

Design a deterministic finite automata which accepts set of strings such that every string containing "00" as sub-string but not "000" as sub-string.

[7 Marks]

b)

Show that if $L$ is regular, so $L - \{\epsilon\}$ will be also regular.

[7 Marks]

Q4

Answer the following:

a)

Write a regular expression over alphabets $\{a, b, c\}$ contains at least one "a" and at least one "b".

[7 Marks]

b)

Prove that $L = \{ 0^n 1^m \mid n \leq m \}$ is not regular language.

[7 Marks]

Q5

Answer the following:

a)

What do you mean by closer properties of regular language? Define some important closer properties.

[7 Marks]

b)

Prove that, if $L1$ and $L2$ is regular, then $L1 \cup L2$ is also regular language.

[7 Marks]

Q6

Answer the following:

a)

Explain ambiguities in context free grammar and languages.

[7 Marks]

b)

Find context free grammar for the regular expression $r = (a + b)^*$ .

[7 Marks]

Q7

Answer the following:

a)

Show that the following grammar is ambiguous : $S \rightarrow AB \mid aaB$ $A \rightarrow a \mid Aa$ $B \rightarrow b$

[7 Marks]

b)

Define parse tree with its applications in finite automata.

[7 Marks]

Q8

Answer the following:

a)

What do you mean by push down automata? Explain its move.

[7 Marks]

b)

Using pumping lemma, prove that language $L = \{ WW \mid W \in \{a, b\}^* \}$ is not context free.

[7 Marks]

Q9

Answer the following:

a)

Explain turing machine for computing function.

[7 Marks]

b)

Write in brief about NP complete problem.

[7 Marks]

2014 051611

B.Tech Examination, 2014

Time 3 hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Questions

Q1

Choose the correct option of the following (any seven) :

a)

The output of the Moore machine depends (i) only on present state (ii) only on current input symbol (iii) both on present state and current input symbol (iv) None of the above

b)

The logic of pumping lemma is a good example of (i) the pigeon-hole principle (ii) the divide and conquer technique (iii) recursion (iv) iteration

c)

Recursively enumerable languages are not closed under (i) union (ii) intersection (iii) complementation (iv) concatenation

d)

The language $L = \{a^n b^n a^n, \text{where } n = 1, 2, 3, \dots\}$ is a (i) regular language (ii) context-free language (iii) non-context-free language (iv) None of the above

e)

A language $L$ is denoted by a regular expression $L = (x)^* (x | yx^*)$ . Which of the following is not a legal string within $L$ ? (i) $x$ (ii) $xyxyx$ (iii) $xyx$ (iv) None of the above

f)

Context-free languages are not closed under (i) union (ii) intersection (iii) concatenation

g)

Recursive languages are (i) a proper superset of CFLs (ii) always recognizable (iii) also called type 0 languages (iv) recognizable by Turing machines

h)

Choose the incorrect statement : (i) Every subset of a countable set is countable (ii) The class of DPDA is not countable (iii) The class of TMs is countable (iv) The class of LBA is countable

i)

Which of the following statements is true? (i) The language $\{a^n \mid n \text{ is prime}\}$ is regular language (ii) The union of 2 recursive languages is recursive (iii) Recursive enumerable languages are closed under complementation (iv) Recursive languages are not closed under complementation

j)

In case of TM, by reading input $x$ , TM (i) may go to halt-final state (ii) may go to halt-non-final state (iii) may go to infinite loop (iv) All of the above

[14 Marks]

Q2

Answer the following:

a)

Obtain the regular expression for the following sets :

[10 Marks]

b)

Differentiate between Moore and Mealy machines.

[2 Marks]

c)

Differentiate between NFA and DFA.

[2 Marks]

Q3

Answer the following:

a)

Construct NFA equivalent to the following regular expression : $10 | (0 | 11)0^* 1$ .

[4 Marks]

b)

Construct an NFA for the following set : Set of all strings over $\Sigma = \{0, 1\}$ containing at least two 0's.

[5 Marks]

c)

Construct NFA for the set of strings over $\Sigma = \{0, 1\}$ of alternate 0's and 1's.

[5 Marks]

Q4

Answer the following:

a)

Construct a DFA for the regular expression $r = (ab | ba)^* aa(ab | ba)$ .

[7 Marks]

b)

Find out the regular expression for the following FA : [Table required]

[7 Marks]

Q5

Answer the following:

a)

Construct a Moore machine equivalent to the following Mealy machine : [Table required]

[5 Marks]

b)

Prove the following two properties : (i) Regular sets are closed over the union operation (ii) Regular sets are closed over the intersection operation.

[5 Marks]

c)

Show with the help of pumping lemma that the following language is not regular : $L = \{ a^p \mid p \text{ is prime number} \}$ .

[4 Marks]

Q6

Answer the following:

a)

Give the CFG for the following languages :

[6 Marks]

b)

Find a CFG for the following regular expression : $r = (baa | abb)^*$ .

[4 Marks]

c)

Let $G$ be a context-free grammar, which is defined as $S \rightarrow aSb | ab$ . Find the CFL generated by $G$ .

[4 Marks]

Q7

Answer the following:

a)

Find a regular grammar for the following regular expression : $r = (abbb | ba)^* ab$ .

[4 Marks]

b)

Determine a CFG without unit production equivalent to the CFG given below : $S \rightarrow ABCD; A \rightarrow a; B \rightarrow C | b; C \rightarrow D; D \rightarrow c$.

[3 Marks]

c)

Find the CNF (Chomsky Normal Form) for the following CFG : $S \rightarrow aAbB; A \rightarrow Ab | b; B \rightarrow Ba | a$.

[3 Marks]

d)

Eliminate the null productions from the following CFG : $S \rightarrow ABA; A \rightarrow aA | \epsilon; B \rightarrow bB | \epsilon$.

[4 Marks]

Q8

Answer the following:

a)

Prove that the CFL's are not closed under intersection.

[3 Marks]

b)

Design a PDA to accept the language $L = \{ a^n b^{2n} \mid n \geq 1 \}$ by empty stack.

[4 Marks]

c)

Design a PDA to accept the language $L = \{ wcw^R \mid w \in \{a, b\}^+ \}$ by empty stack.

[4 Marks]

d)

Prove using pumping lemma that the following language is not CFL : $L = \{ a^i b^i c^i \mid i \geq 1 \}$ .

[3 Marks]

Q9

Answer the following:

a)

Design a TM over $\{a, b, c\}$ to accept the language $L = \{ ww^R \mid w \in \{a, b\}^+ \}$ .

[7 Marks]

b)

Design a Turing machine for the regular expression $011^*$ .

[7 Marks]

2013 105301

B.Tech Examination, 2013

Time 3 hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Questions

Q1

Answer the following:

a)

Explain the differences between NFA and DFA.

[7 Marks]

b)

Design a DFA which accepts all strings which are ending with 101 over an alphabet {0, 1}.

[7 Marks]

Q2

Answer the following:

a)

Obtain the regular expression for the following sets :

[7 Marks]

b)

Construct an NFA (without using Thompson's rule) for the following set : Set of strings over $\Sigma = \{0, 1\}$ with alternate 0's and 1's.

[7 Marks]

Q3

Answer the following:

a)

Give DFA for the following NFA ($s$ is the final state) : [Table required]

[7 Marks]

b)

Construct an NFA using $\epsilon$ move for $r = (b | c)^* a (b | c)^*$ .

[7 Marks]

Q4

Answer the following:

a)

Give DFA for the NFA constructed in Question No. 3 (b).

[7 Marks]

b)

Find out the regular expression for the following transition diagram : [Diagram required]

[7 Marks]

Q5

Answer the following:

a)

Design a Moore machine to determine the residue mode 4 for each binary string treated as integer.

[7 Marks]

b)

Design a Mealy machine that uses its state to remember the last symbol read and emits output $y$ whenever current input matches the previous one, and emits $n$ otherwise.

[7 Marks]

Q6

Answer the following:

a)

Construct a Moore machine equivalent to the following Mealy machine : [Table required]

[7 Marks]

b)

Show using pumping lemma that the language $L = \{ a^i b^i \mid i \geq 1 \}$ is regular or not.

[7 Marks]

Q7

Answer the following:

a)

Reduce the grammar $G$ given by $S \rightarrow aAa; A \rightarrow Sb / bcc / DaA; C \rightarrow abb / DD; E \rightarrow ac; D \rightarrow aDA$ into an equivalent grammar by removing useless symbols and useless productions from it.

[7 Marks]

b)

Convert the following grammar into CNF : $S \rightarrow aAD; A \rightarrow aB / bAB; B \rightarrow b; D \rightarrow d$

[7 Marks]

Q8

Answer the following:

a)

Let $G$ be the grammar given by $S \rightarrow aABB / aAA; A \rightarrow aBB / a; B \rightarrow bBB / A$ Construct the PDA that accepts the language generated by this grammar $G$ .

[7 Marks]

b)

Define deterministic push-down automata. Explain with an example.

[7 Marks]

Q9

Answer the following:

a)

Give a Turing machine—that computes one's complement of a binary number;

[7 Marks]

b)

Give a Turing machine—that shifts the input string over the alphabet $\{0, 1\}$ by one position right by inserting '#' as the first character.

[7 Marks]

Q10

Answer the following:

a)

Explain about deterministic context-free language and deterministic PDA.

[7 Marks]

b)

Show that $L = \{ a^n b^n c^n : n \geq 1 \}$ is a CSL.

[7 Marks]