# Multiple choice question for engineering

## Set 1

1. If L is a language, the reversal of the language can be represented as:

a) L’

b) L^{c}

c) L^{r}

d) more than one option is correct

### View Answer

^{r}is defined as the reversal of a language. L

^{r}is a set of strings whose reversal is in L. Example: L={0, 01, 100} Lr={0, 10, 001}

2. If L is a regular language, ____ is also regular.

a) L^{r}

b) L’

c) L*

d) All of the mentioned

### View Answer

^{r}, L’, L* i.e. reversal, complementation and kleene all are the closure properties of regular language.

3. If E=F+G;

E^{r}=?

a) F^{r}+G^{r}

b) (F+G)^{r}

c) Both (a) and (b)

d) None of the mentioned

### View Answer

4. If E= FG, E^{r}=?

a) F^{r}G^{r}

b) G^{r}F^{r}

c) Both (a) and (b)

d) None of the mentioned

### View Answer

^{r}=G

^{r}F

^{r}. Example: (01*)R=(1*)R(0)R

5. Simplify the following identity:

E=01*+10*

E^{R}=?

a) (1*0+0*1)

b) (01*10*)^{R}

c) (0*1+10*)

d) All of the mentioned

### View Answer

^{R}+(10*)

^{R}=>(1*)

^{R}0

^{R}+(0*)

^{R}1

^{R}=>1*0+0*1

6. Which of the following obey the closure properties of Regular language?

a) Homomorphism

b) Inverse Homomorphism

c) Reversal

d) All of the mentioned

### View Answer

7. Let h(L) be a language of regular expression abe*+e(ab)*. Simplify the h(L)

a) (ab)*+eab*

b) abe*+ea*b*

c) (ab)*

d) None of the mentioned

### View Answer

8. Let h(0)=ab; h(1)=e

Let L={abab,baba}

h-1(L)=_______

a) the language of two one’s and any number of zeroes

b) the language of two zeroes and any number of one’s

c) the language of two zeroes and two one’s

d) none of the mentioned

### View Answer

9. While proving Inverse Homomorphism, which of the following steps are needed?

a) Start with a DFA Ain L

b) Construct a DFA B for h-1(L)

c) The set of states, initial and final states should be same.

d) All of the mentioned

### View Answer

10. 8. Let h(0)=ab; h(1)=e

Let L={abab,baba}

h-1(L)= the language of two zeroes and any number of one’s.

The given example belongs to which of the following?

a) Homomorphism

b) Inverse Homomorphism

c) Both (a) and (b)

d) None of the mentioned

### View Answer

## Set 2

1. According to the rice’s theorem, If P is a non trivial property, Lp is :

a) infinite

b) decidable

c) undecidable

d) none of the mentioned

### View Answer

2. Fill in the blank with reference to Rice’s theorem.

For any non-trivial property of __________ no general or effective method can decide whether an algorithm computes it with that property.

a) partial functions

b) piecewise functions

c) both (a) and (b)

d) none of the mentioned

### View Answer

3. Which of the following is incorrect according to rice theorem?

Let S be a set of language hat is non trivial:

a) there exists a TM that recognizes the language in S

b) there exists a TM that recognizes the language not in S

c) both (a) and (b)

d) none of the mentioned

### View Answer

4. Which of the following set of computable functions are decidable?

a) The class of computable functions that are constant, and its complement

b) The class of indices for computable functions that are total

c) The class of indices for recursively enumerable sets that are cofinite

d) All of the mentioned

### View Answer

5. Which of the following statements are undecidable?

For a given Turing Machine M,

a) does M halt on an empty input tape

b) does M halt for anly inputs at all?

c) is L(M) regular? Context free? Turing decidable?

d) all of the mentioned

### View Answer

6. Post Correspondence problem is

a) decidable decision problem

b) undecidable decision problem

c) not a decision problem

d) none of the mentioned

### View Answer

7. State true or false:

Statement: The difference between PCP and MPCP is that in MPCP, a solution is required to start with the first string on each list.

a) true

b) false

### View Answer

8. PCP stands for?

a) Post Correspondence Problem

b) Post Corresponding Problem

c) Pre Correspondence problem

d) None of the mentioned

### View Answer

9. Can a Modified PCP problem be reduced to PCP?

a) yes

b) no

### View Answer

10. Consider three decision problem A, B, C. A is decidable and B is not. Which of the following is a correct option?

a) C is undecidable if C is reducible to B

b) C is undecidable if B is reducible to C

c) C is decidable if A is reducible to C

d) C is decidable if C is reducible to B’s complement.

### View Answer

## Set 3

1. State true or false:

Statement: Every right-linear grammar generates a regular language.

a) True

b) False

### View Answer

2. What the does the given CFG defines?

S->aSbS|bSaS|e and w denotes terminal

a) wwr

b) wSw

c) Equal number of a’s and b’s

d) None of the mentioned

### View Answer

3. If L1 and L2 are context free languages, which of the following is context free?

a) L1*

b) L2UL1

c) L1.L2

d) All of the mentioned

### View Answer

4. For the given Regular expression, the minimum number of variables including starting variable required to derive its grammar is:

(011+1)*(01)*

a) 4

b) 3

c) 5

d) 6

### View Answer

5. For the given Regular expression, the minimum number of terminals required to derive its grammar is:

(011+1)*(01)*

a) 4

b) 3

c) 5

d) 6

### View Answer

6. A grammar G=(V, T, P, S) is __________ if every production taken one of the two forms:

B->aC

B->a

a) Ambiguous

b) Regular

c) Non Regular

d) None of the mentioned

### View Answer

7. Which among the following is a CFG for the given Language:

L={x∈{0,1}*|number of zeroes in x=number of one’s in x}

a) S->e|0S1|1S0|SS

b) S->0B|1A|e A->0S B->1S

c) All of the mentioned

### View Answer

8. Which of the following languages are most suitable for implement context free languages ?

a) C

b) Perl

c) Assembly Language

d) None of the mentioned

### View Answer

9. Which among the following is the correct grammar for the given language?

L={x∈{0,1}*|number of zeroes in x¹number of one’s in x}

a) S-> 0|SS|1SS|SS1|S1S

b) S-> 1|0S|0SS|SS0|S0S

c) S-> 0|0S|1SS|SS1|S1S

d) None of the mentioned

### View Answer

10. L={0^{i}1^{j}2^{k} | j>i+k}

Which of the following satisfies the language?

a) 0111100

b) 011100

c) 0001100

d) 0101010

### View Answer

## Set 4

1.Given Language: L= {xϵ∑= {a, b} |x has a substring ‘aa’ in the production}. Which of the corresponding representation notate the same?

a)

b)

c)

d)

### View Answer

2.Let u=’1101’, v=’0001’, then uv=11010001 and vu= 00011101.Using the given information what is the identity element for the string?

a) u^{-1}

b) v^{-1}

c) u^{-1}v^{-1}

d) ε

### View Answer

3.Which of the following substring will the following notation result?

a) 0101011

b) 0101010

c) 010100

d) 100001

### View Answer

4.Predict the following step in the given bunch of steps which accepts a strings which is of even length and has a prefix=’01’

δ (q0, ε) =q0 < δ(q0,0) =δ (δ (q0, ε),0) =δ(q0,0) =q1 < _______________

a) δ (q0, 011) =δ (δ (q0,1), 1) =δ (q2, 1) =q3

b) δ (q0, 01) =δ (δ (q0, 0), 1) = δ (q1, 1) =q2

c) δ (q0, 011) =δ (δ (q01, 1), 1) =δ (q2, 0) =q3

d) δ (q0, 0111) =δ (δ (q0, 011), 0) = δ (q3, 1) =q2

### View Answer

5. Fill the missing blank in the given Transition Table:

Language L= {xϵ∑= {0,1} |x accepts all the binary strings not divisible by 3}

a) Q0

b) Q1

c) Q2

d) No Transition

### View Answer

6.Which among the following is the missing transition in the given DFA?

L= {xϵ∑= {a, b} | x starts with a and ends with b}

a) δ (q0, a) =q0

b) δ (F, a) =q1

c) δ (F, a) =D

d) δ (q1, a) =D

### View Answer

7.The complement of a language will only be defined when and only when the __________ over the language is defined.

a) String

b) Word

c) Alphabet

d) Grammar

### View Answer

8.Which among the following is not notated as infinite language?

a) Palindrome

b) Reverse

c) Factorial

d) L={ab}*

### View Answer

9.Which among the following states would be notated as the final state/acceptance state?

L= {xϵ∑= {a, b} | length of x is 2}

a) q1

b) q2

c) q1, q2

d) q3

### View Answer

10.Which of the following are the final states in the given DFA according to the Language given.?

L= {xϵ∑= {a, b} |length of x is at most 2}

a) q0, q1

b) q0, q2

c) q1, q2

d) q0, q1, q2

### View Answer

## Set 5

1. Fill in the blank with an appropriate option.

In automata theory, ___________ is said to be Computationally Universal if can be used to simulate any single taped Turing Machine.

a) Computer’s instruction set

b) A programming language

c) Cellular Automaton

d) All of the mentioned

### View Answer

2. Give a classic example of the concept of turing complete.

a) lambda calculus

b) C++

c) Lisp

d) All of the mentioned

### View Answer

3. Let two machines be P and Q. The state in which P can simulate Q and Q can simulate P is called:

a) Turing Equivalence

b) State Equivalence

c) Universal Turing Machine

d) None of the mentioned

### View Answer

4. Which of the following remarks the given statement?

Statement: Any function whose values can be computed by an algorithm, can be computed by a Turing machine.

a) Smn theorem

b) Structured Program theorem

c) Church-Turing thesis

d) None of the mentioned

### View Answer

5. Which of the following can be used to simulate any turing machine?

a) Finite State Automaton

b) Universal Turing Machine

c) Counter machines

d) All of the mentioned

### View Answer

6. State true or false:

Statement: Inorder to show something is Turing complete, it is enough to demonstrate that it can be used to simulate some Turing complete system.

a) true

b) false

### View Answer

7. Which of the following can lack in a Universal computer?

a) Turing Complete Instruction set

b) Infinite memory

c) Infinite time

d) None of the mentioned

### View Answer

8. Which among are not the results of computational theory?

a) In general, it is impossible to predict that what a Turing-complete program will do over an arbitrarily long time.

b) It is impossible to determine for every input, whether the program will eventually stop or continue forever.

c) It is not possible to determine whether a program will return true or false.

d) None of the mentioned

### View Answer

9. Which of the games fill under the category of Turing-complete?

a) Minecraft

b) Minesweeper

c) Dwarf Fortress

d) All of the mentioned

### View Answer

10. Which of the following a Non-turing Complete language?

a) Regular Language

b) Context free grammars

c) Epigram

d) All of the mentioned