Question:medium

Consider the language $L$ over the alphabet $\{0,1\}$: \[ L = \{\, w \in \{0,1\}^* \;\mid\; \text{$w$ does not contain three or more consecutive $1$'s}\,\}. \] The minimum number of states in a Deterministic Finite-State Automaton (DFA) for $L$ is ________.

Show Hint

For “forbid $k$ consecutive symbols” over $\{0,1\}$, a minimal DFA typically needs $k+1$ states: one for each count of trailing forbidden symbols ($0$ to $k-1$) plus a dead state.

Updated On: Jan 31, 2026

Show Solution

Correct Answer: 4

Solution and Explanation

Was this answer helpful?

Questions Asked in GATE CS exam

With respect to a TCP connection between a client and a server, which of the following is true?

GATE CS - 2026
Computer Networks

View Solution

Let $P, Q, R, S$ be relational schemas. Let ``$\rightarrow$'' indicate a functional dependency (FD) in this context. Which of the following best describes the meaning of a functional dependency?

GATE CS - 2026
Database Management Systems

View Solution

A certain processor uses a fully associative cache of size 16 kB. The cache block size is 16 bytes. Assume that the main memory is byte addressable and uses a 32-bit address. How many bits are required for the Tag and the Index fields respectively in the addresses generated by the processor?

GATE CS - 2026
Computer Organization and Architecture

View Solution

Consider $Z = X - Y$, where $X$, $Y$ and $Z$ are all in sign-magnitude form. $X$ and $Y$ are each represented in $n$ bits. To avoid overflow, the representation of $Z$ would require a minimum of:

GATE CS - 2026
Computer Organization and Architecture

View Solution

Consider the language \(L\) over the alphabet \(\{0,1\}\): \[ L = \{\, w \in \{0,1\}^* \;\mid\; \text{$w$ does not contain three or more consecutive $1$'s}\,\}. \] The minimum number of states in a Deterministic Finite-State Automaton (DFA) for \(L\) is ________.

Show Hint

Correct Answer: 4

Solution and Explanation

Top Questions on Theory of Computations

Questions Asked in GATE CS exam