Which of the following cannot be the number of states in the minimal DFA equivalent to the NFA of 6 states?
Solution :
The correct options are 65 and 128.
To understand why these cannot be the number of states, let us analyze the relation between the number of states in a Non-Deterministic Finite Automaton (NFA) and its equivalent Minimal Deterministic Finite Automaton (DFA).
Given that the NFA has n = 6 states, the power set construction method allows us to construct an equivalent DFA. Since the set of states of the DFA is a subset of the power set of the NFA states, the maximum number of states in the equivalent DFA (before minimization) is:
Thus, any DFA equivalent to a 6-state NFA can have at most 64 states. Minimizing a DFA can only decrease (or keep equal) the number of states, but it cannot increase them. Therefore, the number of states in the minimal DFA equivalent to a 6-state NFA must be at most 64.
Let us evaluate the given options against this upper limit of 64 states:
1. 1: This is less than or equal to 64, so it is a possible number of states.
2. 32: This is less than or equal to 64, so it is a possible number of states.
3. 65: Since 65 > 64, it is impossible for the minimal DFA to have 65 states.
4. 128: Since 128 > 64, it is impossible for the minimal DFA to have 128 states.
Consequently, the values 65 and 128 cannot be the number of states in the minimal DFA equivalent to the 6-state NFA.
Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.
Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.
Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.
A comprehensive CUET UG Mathematics Question Paper with Solutions – 2 June 2023 (Shift 3) designed to help students practice and understand the actual CUET exam pattern. This paper covers important topics from Algebra, Calculus, Coordinate Geometry, Probability, Statistics, Matrices, Determinants, and Vectors, featuring a balanced mix of conceptual, numerical, and application-based questions. Detailed solutions are provided to strengthen problem-solving skills, improve conceptual clarity, and enhance calculation accuracy. Based on the CUET syllabus and previous year exam trends, this paper is ideal for practice, revision, self-assessment, time management, previous year analysis, and final preparation for upcoming CUET UG Mathematics examinations.
A comprehensive CUET Accountancy Question Paper – 20 June 2023 (Shift 2) designed to help students practice and analyze previous year exam patterns for effective CUET preparation. This paper covers important topics including Accounting for Partnership Firms, Company Accounts, Financial Statements Analysis, Cash Flow Statements, Accounting Ratios, and Fundamental Accounting Principles. It features a balanced mix of conceptual, numerical, and application-based questions to strengthen accounting concepts, improve calculation accuracy, and enhance problem-solving skills. Based on the CUET exam structure and syllabus, this paper is ideal for practice, revision, self-assessment, time management, previous year analysis, and final preparation for upcoming CUET Accountancy examinations.
Copyright © 2026 Combe Labs Private Limited. All Rights Reserved.