1. How many languages are over the alphabet R?

a) countably infinite

b) countably finite

c) uncountable finite

d) uncountable infinite

### View Answer

Answer: d

Explanation: A language over an alphabet R is a set of strings over A which is uncountable and infinite.

Explanation: A language over an alphabet R is a set of strings over A which is uncountable and infinite.

a) making starting state as final state.

b) no trival method.

c) making final states non-final and non-final to final.

d) make final as a starting state.

### View Answer

Answer:c

Explanation: String accepted in previous DFA will not be accepted and non accepting string will be accepted .

Explanation: String accepted in previous DFA will not be accepted and non accepting string will be accepted .

Language: {0,01}

a) 0+01

b) {0} U {01}

c) {0} U {0}{1}

d) {0} ^ {01}

### View Answer

Answer: d

Explanation: The given option represents {0, 01} in different forms using set operations and Regular Expressions. The operator like ^, v, etc. are logical operation and they form invalid regular expressions when used.

Explanation: The given option represents {0, 01} in different forms using set operations and Regular Expressions. The operator like ^, v, etc. are logical operation and they form invalid regular expressions when used.

R=Q + RP has a unique solution:

a) Q*P

b) QP*

c) Q*P*

d) (P*O*) *

### View Answer

Answer: b

Explanation: The given statement is the Arden’s Theorem and it tends to have a unique solution as QP*.

Let P and Q be regular expressions,

R=Q+RP

R=Q+(Q+RP) P

R=Q+((Q+RP) +RP) +P=Q+QP+RPP+RPP=Q+QP+(Q+RP) PP+(Q+RP) PP=Q+QP+QPP+RPPP+QPP+RPPP,

If we do this recursively, we get:

R= QP*

Explanation: The given statement is the Arden’s Theorem and it tends to have a unique solution as QP*.

Let P and Q be regular expressions,

R=Q+RP

R=Q+(Q+RP) P

R=Q+((Q+RP) +RP) +P=Q+QP+RPP+RPP=Q+QP+(Q+RP) PP+(Q+RP) PP=Q+QP+QPP+RPPP+QPP+RPPP,

If we do this recursively, we get:

R= QP*

a) e

b) ?

c) ?

d) None of the mentioned

### View Answer

Answer: a

Explanation: The star operation brings together any number of strings from the language to get a string in the result. If the language is empty, the star operation can put together 0 strings, resulting only the empty string.

Explanation: The star operation brings together any number of strings from the language to get a string in the result. If the language is empty, the star operation can put together 0 strings, resulting only the empty string.

P(x): String of length 6 or less for å={0,1}*

a) (1+0+e)6

b) (10)6

c) (1+0)(1+0)(1+0)(1+0)(1+0)(1+0)

d) More than one of the mentioned is correct

### View Answer

Answer: a

Explanation: As the input variables are under Kleene Operation, we need to include e,thus option c is not correct,thereby option (a) is the right answer.

Explanation: As the input variables are under Kleene Operation, we need to include e,thus option c is not correct,thereby option (a) is the right answer.

a) b*a*

b) (a*b*)*

c) a*b*

d) none of the mentioned

### View Answer

Answer : b

Explanation : None.

Explanation : None.

a) Every subset of a regular set is regular

b) Every finite subset of non-regular set is regular

c) The union of two non regular set is not regular

d) Infinite union of finite set is regular

### View Answer

Answer : b

Explanation : None.

Explanation : None.

?= {a, b, c, d}

a) 4+4

b) 4+16

c) 4+0

d) depends on the Language

### View Answer

Answer: d

Explanation: The out degree for a DFA I fixed while the in degree depends on the number of states in the DFA and that cannot be determined without the dependence over the Language.

Explanation: The out degree for a DFA I fixed while the in degree depends on the number of states in the DFA and that cannot be determined without the dependence over the Language.

a) n+1

b) n

c) n-1

d) n+2

### View Answer

Answer: a

Explanation: The maximum number of final states for a DFA can be total number of states itself and minimum would always be 1, as no DFA exits without a final state. Therefore, the solution is n+1.

Explanation: The maximum number of final states for a DFA can be total number of states itself and minimum would always be 1, as no DFA exits without a final state. Therefore, the solution is n+1.

a) Conversion of NFA to DFA

b) DFA minimization

c) Eliminating Null references

d) e-NFA to NFA

### View Answer

Answer: a

Explanation: The conversion of a non-deterministic automata into a deterministic one is a process we call subset construction or power set construction.

Explanation: The conversion of a non-deterministic automata into a deterministic one is a process we call subset construction or power set construction.

12. There exists an initial state, 17 transition states, 7 final states and one dumping state, Predict the maximum number of states in its equivalent DFA?

a) 226

b) 224

c) 225

d) 223

### View Answer

Answer: a

Explanation: The maximum number of states an equivalent DFA can comprise for its respective NFA with k states will be 2k.

Explanation: The maximum number of states an equivalent DFA can comprise for its respective NFA with k states will be 2k.

13. State true or false?

Statement: e (Input) does not appears on Input tape.

a) True

b) False

Answer: a

### View Answer

Explanation: e does not appears on Input tape, e transition means a transition without scanning a symbol i.e. without moving the read head.

a) 3 * 28

b) 2(3*8)

c) 2(3+8)

d) None of the mentioned

### View Answer

Answer:b

Explanation: 2(m*n) states requires .

Explanation: 2(m*n) states requires .

a) 1

b) 2

c) 3

d) Its primary function, not in any phase

### View Answer

Answer: a

Explanation: The first phase of compilation process is called lexical analysis. It fragments the source code into token which is the smallest programming unit of a program.

Explanation: The first phase of compilation process is called lexical analysis. It fragments the source code into token which is the smallest programming unit of a program.