Register

GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 43

• retagged by
774 views
8 votes
8 votes

Let $\text{D}$ be a DFA with $n$ states $\& \;\text{N}$ be an NFA with $n$ states. Which of the following is/are true?

  1. If $\text{D}$ accepts some string of length $n$, then the language of $\text{D}$ is infinite.
  2. If $\text{D}$ accepts some string of length $n-1$, then the language of $\text{D}$ is infinite.
  3. If $\mathrm{N}$ accepts some string of length $n$, then the language of $\mathrm{N}$ is infinite.
  4. If $\mathrm{N}$ accepts some string of length $n-1$, then the language of $\mathrm{N}$ is infinite.
• retagged by
User Avatar

1 Answer

7 votes
7 votes
If the DFA has $n$ states, and the language contains any string of length $n-1$ or more, then the language is infinite.

If the NFA has $n$ states, and the language contains any string of length $n$ or more, then the language is infinite.
• edited by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

598
views
1 answers
2 votes
GO Classes asked Jan 21
598 views
GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 42
Consider the following context-free language: $L_1=\left\{a^m b^n c^n \mid n, m \geq 0\right\}$. Which of the following choices of language $L_2$ ... $L_2=\left\{a^k b^{2 k} c^{2 k} \mid k \geq 0\right\}$
User Avatar
624
views
2 answers
3 votes
GO Classes asked Jan 21
624 views
GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 44
Which of the following statements is/are false?Let $\text{A}$ and $\text{B}$ be sets of languages over some fixed alphabet $\Sigma$, with $\text{A} \subseteq \text{B}$. ... $\subseteq \mathrm{L} 1$, then $\mathrm{L} 2$ is decidable.)
User Avatar
563
views
1 answers
2 votes
GO Classes asked Jan 21
563 views
GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 33
Consider the following grammar:$\begin{aligned}& S \rightarrow a S^{\prime} \\& S^{\prime} \rightarrow b S^{\prime} \mid \epsilon\end{aligned}$Which of the following is/are ... $bS'$a S^{\prime} b$bbS$
User Avatar
1.0k
views
1 answers
6 votes
GO Classes asked Jan 21
1,006 views
GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 36
Let $A, B, C$ be events such that $P(A)=P(B)=P(C)=0.5, P(A \cap B)=0.3, P(A \cap C)=0$.Which of the following is/are true?$P(A \cup B)=0.75$P(A \cup C)=1$P(B \cap C)=0.23$P(B \cup C)=0.9$
User Avatar
Link Copied!