Q61GATE 2005MCQ

Let $N_{f}$ and $N_{p}$ denote the classes of languages accepted by non-deterministic finite automata and non- deterministic push-down automata, respectively. Let $D_{f}$ and $D_{p}$ denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata respectively. Which one of the following is TRUE?

🚀 Solve in Practice Mode

Q62GATE 2005MCQ

Consider the machine M: The language recognized by M is :

🚀 Solve in Practice Mode

Q63GATE 2004MCQ

The following finite state machine accepts all those binary strings in which the number of 1's and 0's are respectively.

🚀 Solve in Practice Mode

Q64GATE 2004MCQ

Let $M=(K, \Sigma,\sigma ,s, F)$ be a finite state automaton, where $K=\{A, B\}, \Sigma=\{a, b\}, s=A, F=\{B\}$ $\sigma(A, a)=A, \sigma(A, b)=B, \sigma(B, a)=B \text { and } \sigma(B, b)=A$ A grammar to generate the language accepted by M can be specified as $G=(V, \Sigma, R, S), \text { where } V=K \cup \Sigma, \text { and } S=A$ Which one of the following set of rules will make L(G) = L(M) ?

🚀 Solve in Practice Mode

Q65GATE 2003MCQ

Consider the NFA M shown below. Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true ?

🚀 Solve in Practice Mode

Q66GATE 2003MCQ

Consider the following deterministic finite state automaton M. Let S denote the set of seven bit binary strings in which the first, the fourth, and the last bits are 1. The number of strings in S that are accepted by M is

🚀 Solve in Practice Mode

Q67GATE 2002MCQ

The finite state machine described by the following state diagram with A as starting state, where an arc label is x/y and x stands for 1-bit input and y stands for 2-bit output.

🚀 Solve in Practice Mode

Q68GATE 2002MCQ

The smallest finite automaton which accepts the language {x length of x is divisible by 3} has

🚀 Solve in Practice Mode

Q69GATE 2001MCQ

Given an arbitary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least.

🚀 Solve in Practice Mode

Q70GATE 2001MCQ

Consider a DFA over $\Sigma$ = {a,b} accepting all strings which have number of a's divisible by 6 and number of b's divisible by 8. What is the minimum number of states that the DFA will have ?

🚀 Solve in Practice Mode

Q71MCQ

What can be said about a regular language L over {a} whose minimal finite state automaton has two states?

🚀 Solve in Practice Mode

Q72MCQ

Consider the regular expression (0 + 1) (0+1) ... n times. The minimum state finite automaton that recognizes the language represented by this regular expression contains

🚀 Solve in Practice Mode

Q73MCQ

Let L be the set of all binary strings whose last two symbols are the same. The number of states in the minimal state deterministic finite state automaton accepting L is

🚀 Solve in Practice Mode

Q74MCQ

Which of the following set can be recognized by a Deterministic Finite state Automaton?

🚀 Solve in Practice Mode

Q75MCQ

Regarding the power of recognition of languages, which of the following statements is false?

🚀 Solve in Practice Mode

Q76MCQ

Consider the following state table shown in figure for a sequential machine. The number of states in the minimized machine will be

\begin{array}{|l|l|ll|}\hline \text{} & \text{} & \textbf{Input}\\ \hline && \text{0} & \text{1} \\ \hline \textbf{Present State} & \textbf{A} & \text{D,0} & \text{B,1} \\ \text{} & \textbf{B} & \text{A,0} & \text{C,1}\\ & \textbf{C} & \text{A,0} & \text{B,1} \\ \text{} & \textbf{D} & \text{A,1} & \text{C,1} \\ \hline \text{} & \text{} & \textbf{Next state, Output}\\ \hline \end{array}

🚀 Solve in Practice Mode

Q77MCQ

A finite state machine with the following state table has a single input x and a single out z.

\begin{array}{|c|ll|}\hline \textbf{present state} &\textbf{next state, z} \\ & \text{x=1} & \text{x=0} \\ \hline \text{A} & \text{D,0} & \text{B,0} \\ \hline \text{B} & \text{B,1} & \text{C,1} \\ \hline \text{C} & \text{B,0} & \text{D,1} \\ \hline \text{D} & \text{B,1} & \text{C,0} \\ \hline \end{array}

If the initial state is unknown, then the shortest input sequence to reach the final state C is:

🚀 Solve in Practice Mode

Q78MSQ

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: In which of the cases stated below is the following statement true? "For every non-deterministic machine $M_{1}$ there exists an equivalent deterministic machine $M_{2}$ recognizing the same language".

🚀 Solve in Practice Mode

Q79MediumMCQ

Consider the DFA $A$ given below. Which of the following are FALSE?

🚀 Solve in Practice Mode

📖 Explanation

Complement of $L(A)$ (regular language) is regular and hence also Context Free. True. Regular expression is $(11^*0 +0)(0+1)^*$ . True. Both non-final states are equivalents and can be minimized, so 3 is False. Shortest length string reached from $q0$ to $q1$ (final) is $0$ , so 4 is False. Correct Answer: $D$

Q80MediumMCQ

Consider the following deterministic finite state automaton $M$ . Let $S$ denote the set of seven bit binary strings in which the first, the fourth, and the last bits are $1$ . The number of strings in $S$ that are accepted by $M$ is

🚀 Solve in Practice Mode

📖 Explanation

Language of above DFA is all strings over $\{0,1\}$ that contain substring $001$ . Regular expression of above DFA is $(0+1)^*00\mathbf{1}(0+1)^*$ . $\mathbf{1}$ that is underlined can not be first bit of $7$ -bit binary no, but can be fourth bit or last bit. Case 1: if it is $4$ th bit, possible set of strings $= 4$ strings. Case 2: if it is last bit, possible set of strings $= 4$ strings. String common in both cases is $\mathbf{1}00\mathbf{1}00\mathbf{1}$ . Total strings $= 4 + 4 - 1 = 7$ strings. Correct Answer: $C$