TOC Passage Answers

INSTRUCTIONS:-

1. All correct answers are written with each Question.

2. Because of you Convenience we have typed each and every question with their options.

3. Just search few words of the question and you will be redirected to that question.

4. Each and every question in this pdf is 100% correct and checked from various sources.

5. Hope you can score full marks now. WISH YOU ALL THE BEST

1. Turing machine was invented by Alan Turing……… in both directions

1. Which of the following statement is false?

A Turing machine is more powerful than finite state machine because it has halt state

2. Which of the following can TM can perform?

All of the mentioned

3. Select the correct option of a given TM that will accept the one of the following language L

L= {a, b}* {aba}, the language of all strings in {a, b}* that end with aba

4. Given Turing machine will accept one of the following Language L

L= {a, b}* {bb}* {bb} {a, b}*, the language of all strings in {a, b}* that either start with substring
bb or end with bb

5. Given Turing machine will accept one of the following Language L

L= {x x | x {a, b}*}

2. Pumping Lemma….

1.Which of the following is the condition of pumping lemma

The string can split into three parts

2.while applying pumping …….

3.if s is a string….pumping lemma

All of the above

 4.Answer in accordance…

i>=0

5.let w=xyz….

Pumping

3. The language accepted by finite automata can be easily described by simple expressions called
Regular Expressions. Regular expressions can be thought of as the algebraic description of a
regular language. It is the most effective way to represent any language.

1. which of the following regular expression is equivalent to R(1,0)? R(1,0)=(111*)*

(11+111)*
2. Select the regular expression for the language containing the string in which every '0'
is immediately followed by '11'.
(011+1)*
3. Choose the correct regular expression for the language starting with 'a' but not having
consecutive b's.
(a + ab)*
4. Given: Σ={a, b} L= (xe*x is a string combination) 4 represents which among the
following?
{aaaa,abab,E,abaa,aabb

5. The regular sets are closed under intersection' i

true

4. If a context free grammar G has more than one derivation tree for some string w e L(G), it is
called an ambiguous grammar. There exist multiple right-most or left-most derivations for
some string generated from that grammar.

1. Choose the correct option: Statement 1: Recursive Inference, using productions from head
to body. Statement 2: Derivations, using productions from body to head.
True
2. Which ofthe following statements are correct for a concept called inherent ambiguity in
CFL?
Every CFG for L is ambiguous
3. Choose the correct option: Statement: There exists two inference approaches: 1.)
Recursive Inference, 2.) Derivation
True
 4. An expression is mentioned as follows. Figure out number of incorrect notations or
symbols, such that a change in those could make the expression correct. L(G)={w in T* S-
>*W}
0 erros
5. Is the following statement correct? Statement: Recursive inference and derivation are
equivalent
Yes

5. The context sensitive grammar is used to represent context sensitive language. The context
sensitive grammar follows the following rules: 1) The context sensitive grammar may have
more than one symbol on the left hand side of their production rules. 2) The number of
symbols on the left-hand side must not exceed the number of symbols on the right-hand side.
3) The rule of the form A --> & is not allowed unless A is a start symbol. It does not occur on
the right-hand side of any rule. 4) The Type 1 gr

1. Which of the following grammar are in CSG?

Ab --> aBa, Ba ->ссс
2. Suppose P is set of rules and a context-sensitive grammar G is -G=
{(S,A,B,C,a,b,c),(a,b,c),P,S}; S -> aSBC, S-> aBC, CB-> BС, aB-> ab, bB -> bb, bC -> bc, cC->
cc, Then, the language generated by the grammar G is
(a^n b^n c^n | n>= 1}
3. State true or false: Statement: CSL is less general than Unrestricted Grammar and
more general than Context Free Grammar.
True
4. Context Sensitive grammar is recognized by
Linear bound automata
5. The given grammar G is belonging to which of the category? S→ abc/aAbc, Ab → bA,
Ac Bbcc, bB Bb, aBaa/aaA
Context sensitive language

6. A pushdown automaton is a way to implementacontext-free grammar in a similar way we

design DFA for a regular grammar. A DFA can remember a finite amount of information,
but a PDA can remember an infinite amount of information. Basically a pushdown
automaton is - "Finite state machine" + "a stack"
1. A two-way push down automaton (2-PDA) can:
all of the mentioned
2. The acceptance of input strings byapush down automaton can be defined in terms of:
all of the mentioned
3. A pushdown automata can be defined as: (Q, input, G, q0, z0, A, d) What does the
symbol z0 represents?
 initial stack symbol
4. Which is/are true?
1,2,3
5. For a context-free grammar S--> S*S | a | b, the equivalent push down automaton has
transition rule(s):
All of the mentioned

7.Moore machine is a finite state machine in which the next state is decided by the current state and
current input symbol. The output symbol at a given time depends only on the present state ofthe
machine. Moore machine can be described by 6 tuples (Q, q0, Σ,O, 5, λ) where, Q: finite set of states
q0: initial state of machine : finite set of input symbols O: output alphabet 8: transition function where
Q xΣ--> Qλ: output function where Q-->O

1. How many total no. of states required for designing Moore machine which counts the
occurrence of substring 'aab' in input string.

2. How many total no. of states required for the construction of a Moore machine that
determines whether an input string contains an even or odd number of 1's

3. How many total no. of states required for designing Moore machine which determine the
residue mod-3 for each binary string treated as binary integer

4. What is the output for the given language? Language: A set of strings over = {a, b} is taken
as input and it prints 1 as an output "for every occurrence of a "b" as its substring. (INPUT:
abaaab)

0010001

5. Given Turing machine will accept one of the following Language L

6.how many total no….. N as a output

8.Turing Machine was invented by Alan Turing in 1936 and it is used to accept Recursive Enumerable
Languages (generated by Type-0 Grammar). A turing machine consists of a tape of infinite length on
which readand writes operation can be performed. The tape consists of infinite cells on which each
cell either contains input symbol or a special symbol called blank. It also consists of a head pointer
which points to cell currently being read and it can move in both directions.

1. State True or false: Statement: No Turing machine can be considered with more than one
tape.

False

2. Select the correct option of a given TM that willaccept the one of the following language

L= {a, b}* {ab} {a, b}* U {a, b} {ba}, the language of all strings in {a, b} that either contain the
substring "ab" or end with "ba"

3. Which of the following can TM can perform?

All of the mentioned

4. Which of the following statement is false

A Turing machine is more powerful than finite state machine because it has halt state.

5. Given Turing machine will accept one of the following Language L

L={x,x|xE(a,b)*}(doubt)

9. Turing machine was invented in 1936 by Alan Turing. It is an accepting device which accepts
Recursive Enumerable Language generated by type 0 grammar. There are various features of the
Turing machine: It has an external memory which remembers arbitrary long sequence of input. It has
unlimited memory capability. The model has a facility by which the input at left or right on the tape
can be read easily. The machine can produce certain output based on its input. Sometimes it may be
required that the same input has to be used to generate the output. So in this machine, the distinction
between input and output has been removed. Thus a common set of alphabets can be used for the
Turing machine.

1. State true or false: Statement: Two track turing machine is equivalent to a standard turing
machine.

True

2. A turing machine operates over:

infinite memory tape

3. The following turing machine acts like:

Reverse of a string

4. Consider M1 and M2 are two turing machines then the composite can be represented using
the expression:

M1.M2
 5. Given Turing machine will accept one of the following Language

L= (a^i.b.a^j | O<i<j}

10.Arden

1.Qp*

2.True

3.True

4.True

5.Non-null transition

11. Context free grammar is formal grammar…….. CFG

1.not true

Chomsky hierarchy defines only one grammar

2.false

Every nondeterministic pda can be converted to an equivalent deterministic pda

3.true

The union of two context language is context free

4.Tuple v

Set of non terminal

5.A CFG

Context sensitive grammar

12. consider a given Moore …… separated by l

1.if the input 010

1110

2.if input is 010101

1110111

3.if the input is 1011

10010
 4.if the input is 000

1100

5.01110

111110

13.Turning machine ….. can be used for for the turning machine

1.A multitape…

False

2.which of the regular expression…

(a+b)b(a+b)*

3.given transition

Accepts as a palindromes

4.the following tm act like..

Copying a string

5.A turning machine is defined

14.CNF stands for………S-a

1.in which….. find its use

All of the mentioned

2.Let G be a grammar…

Yes

3.which of the following is CNF

S->AB|BC|CD..

4.every grammar in CNF is

Context free

5.which of the following does not have left recursion

GNF(doubt)
15. Regular languages are languages….. explicit formula

1.If L is DFA-regular

DFA regular

2.All the…

1,2,3,4

3.a language is regular if and only if

Accepted by DFA

4.If L1 and L2
Regular
5.To describe
Alphabet
16. Language accepted by…… represent any language
1.none of the above
2.r(st)
3.true
4.(r+s)*=(r*s*)*
5.none of
17. Pushdown automata is a way to implement a CFG in the same way we design DFA for a regular
grammar. A DFA can remember a finite amount of information, but a PDA can remember an infinite
amount of information. Pushdown automata is simply an NFA augmented with an "external stack
memory". The addition of stack is used to provide a last-in-first-out memory management capability
to Pushdown automata. A PDA is more powerful than FA. Any language which can be acceptable by FA
can also be acceptable by PDA. PDA also accepts a class of language which even cannot be accepted by
FA. Thus PDA is much more superior to FA.

1. Which of the following language cannot be accepted by any deterministic push down
automaton?

A language of palindromes(doubt)

2. All strings over {a, b} having equal number of a’s and b’s can be recognized by

PDA

3. Which of the following statement is true?

All of the above.

 4. If a language L is accepted by a PDA, then:

L is accepted by a PDA in which every move either pops top element of the stack or pushes a
single symbol onto stack on the top of symbol that was previously on top, or leaves the stack
unchanged.

5.If L is accepted by a PDA, then L is also accepted by a PDA having:

atmost two states

18. A Mealy machine is a machine in which output symbol depends upon the present input symbol
and present state of the machine. In the Mealy machine, the output is represented with each input
symbol for each state separated by /. The Mealy machine can be described by 6 tuples (Q, q0, ∑, O, δ,
λ') where 1. Q: finite set of states 2. q0: initial state of machine 3. ∑: finite set of input alphabet 4. O:
output alphabet 5. δ: transition function where Q × ∑--> Q 6. λ': output function where Q × ∑ --> O

1. How many states are required to design a Mealy machine for regular expression
(0+1)*(00+11). *Note: In this Mealy machine that use it’s state to remember the last symbol
read, emits output ‘y’ whenever the current input matches the previous one, and emits ‘n’
otherwise.

2. How many states are required for designing a mealy machine which calculates residue mod-
4 for each binary string treated as binary integer

3. The major difference between Mealy and Moore machine is about

Output Variations

4. Output of mealy machine depends on the transition (input) and Present state. True or false?

True

5. Diagram answer

1’s Compliment