GATE Exam > GATE Questions > What is the wrong statement?1) Complement of...
Start Learning for Free
What is the wrong statement?
1) Complement of DFA that accepts those strings where after each ‘ a, always ‘ b ‘ appears, is the DFA that accepts those strings where after ‘ a ‘ never ‘ b ‘ appears.
2) In a language – no. of state in minimal NFA is n, then in worst case, maximum no. of state in equivalent DFA is 2n.
3) Minimal DFA always contains only one dead state.
- a)1
- b)1 & 2
- c)3
- d)none
Correct answer is option 'A'. Can you explain this answer?
| FREE This question is part of | Download PDF Attempt this Test |
Verified Answer
What is the wrong statement?1) Complement of DFA that accepts those s...
For strings where after each ‘ a , always ‘ b ‘ appears, language is-
View all questions of this test
L1= {ab,abab,abb,bbab,.........,bbb,bbbbbb........}
For string where after ‘ a ‘ never ‘ b ‘ appears ,language is-
L2={ε,a,b,aa,ba,,bbb,bbbb.}
Some strings are there on intersection of L1 & L2 (Like bbb, bbbb etc)
So L1 & L 2 are not complementary to each other .
In a language – no. of state in minimal NFA is n, then in worst case, maximum no. of state in equivalent DFA is 2n.
More than one dead state gets combined during minimization of DFA, so DFA contains only one dead state.
Most Upvoted Answer
What is the wrong statement?1) Complement of DFA that accepts those s...
Understanding the Statements
Let's analyze each statement to identify the incorrect one.
1) Complement of DFA
- The statement claims that the complement of a DFA that accepts strings where after each 'a', 'b' always appears is the DFA that accepts strings where after 'a', 'b' never appears.
- This is incorrect. The correct complement would accept strings where there exists at least one 'a' not followed by a 'b'. Thus, the statement is wrong.
2) NFA to DFA State Conversion
- This statement correctly states that if a minimal NFA has n states, the worst-case scenario for the equivalent DFA is having up to 2^n states.
- This is based on the subset construction method used to convert an NFA to a DFA, where each state in the DFA represents a subset of NFA states.
3) Minimal DFA Dead State
- The third statement asserts that a minimal DFA always has only one dead state.
- This is true. In a minimal DFA, there can be one dead state that is distinct from all the accepting states, ensuring that any string leading to this state is rejected.
Conclusion
- The wrong statement is indeed 1, as it misrepresents the relationship between a DFA and its complement concerning strings following the given conditions.
Thus, the correct answer is option 'A'.
Let's analyze each statement to identify the incorrect one.
1) Complement of DFA
- The statement claims that the complement of a DFA that accepts strings where after each 'a', 'b' always appears is the DFA that accepts strings where after 'a', 'b' never appears.
- This is incorrect. The correct complement would accept strings where there exists at least one 'a' not followed by a 'b'. Thus, the statement is wrong.
2) NFA to DFA State Conversion
- This statement correctly states that if a minimal NFA has n states, the worst-case scenario for the equivalent DFA is having up to 2^n states.
- This is based on the subset construction method used to convert an NFA to a DFA, where each state in the DFA represents a subset of NFA states.
3) Minimal DFA Dead State
- The third statement asserts that a minimal DFA always has only one dead state.
- This is true. In a minimal DFA, there can be one dead state that is distinct from all the accepting states, ensuring that any string leading to this state is rejected.
Conclusion
- The wrong statement is indeed 1, as it misrepresents the relationship between a DFA and its complement concerning strings following the given conditions.
Thus, the correct answer is option 'A'.
|
Explore Courses for GATE exam
|
|
Similar GATE Doubts
What is the wrong statement?1) Complement of DFA that accepts those strings where after each ‘ a, always ‘ b ‘ appears, is the DFA that accepts those strings where after ‘ a ‘ never ‘ b ‘ appears.2) In a language – no. of state in minimal NFA is n, then in worst case, maximum no. of state in equivalent DFA is 2n.3) Minimal DFA always contains only one dead state.a)1b)1 & 2c)3d)noneCorrect answer is option 'A'. Can you explain this answer?
Question Description
What is the wrong statement?1) Complement of DFA that accepts those strings where after each ‘ a, always ‘ b ‘ appears, is the DFA that accepts those strings where after ‘ a ‘ never ‘ b ‘ appears.2) In a language – no. of state in minimal NFA is n, then in worst case, maximum no. of state in equivalent DFA is 2n.3) Minimal DFA always contains only one dead state.a)1b)1 & 2c)3d)noneCorrect answer is option 'A'. Can you explain this answer? for GATE 2024 is part of GATE preparation. The Question and answers have been prepared according to the GATE exam syllabus. Information about What is the wrong statement?1) Complement of DFA that accepts those strings where after each ‘ a, always ‘ b ‘ appears, is the DFA that accepts those strings where after ‘ a ‘ never ‘ b ‘ appears.2) In a language – no. of state in minimal NFA is n, then in worst case, maximum no. of state in equivalent DFA is 2n.3) Minimal DFA always contains only one dead state.a)1b)1 & 2c)3d)noneCorrect answer is option 'A'. Can you explain this answer? covers all topics & solutions for GATE 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for What is the wrong statement?1) Complement of DFA that accepts those strings where after each ‘ a, always ‘ b ‘ appears, is the DFA that accepts those strings where after ‘ a ‘ never ‘ b ‘ appears.2) In a language – no. of state in minimal NFA is n, then in worst case, maximum no. of state in equivalent DFA is 2n.3) Minimal DFA always contains only one dead state.a)1b)1 & 2c)3d)noneCorrect answer is option 'A'. Can you explain this answer?.
What is the wrong statement?1) Complement of DFA that accepts those strings where after each ‘ a, always ‘ b ‘ appears, is the DFA that accepts those strings where after ‘ a ‘ never ‘ b ‘ appears.2) In a language – no. of state in minimal NFA is n, then in worst case, maximum no. of state in equivalent DFA is 2n.3) Minimal DFA always contains only one dead state.a)1b)1 & 2c)3d)noneCorrect answer is option 'A'. Can you explain this answer? for GATE 2024 is part of GATE preparation. The Question and answers have been prepared according to the GATE exam syllabus. Information about What is the wrong statement?1) Complement of DFA that accepts those strings where after each ‘ a, always ‘ b ‘ appears, is the DFA that accepts those strings where after ‘ a ‘ never ‘ b ‘ appears.2) In a language – no. of state in minimal NFA is n, then in worst case, maximum no. of state in equivalent DFA is 2n.3) Minimal DFA always contains only one dead state.a)1b)1 & 2c)3d)noneCorrect answer is option 'A'. Can you explain this answer? covers all topics & solutions for GATE 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for What is the wrong statement?1) Complement of DFA that accepts those strings where after each ‘ a, always ‘ b ‘ appears, is the DFA that accepts those strings where after ‘ a ‘ never ‘ b ‘ appears.2) In a language – no. of state in minimal NFA is n, then in worst case, maximum no. of state in equivalent DFA is 2n.3) Minimal DFA always contains only one dead state.a)1b)1 & 2c)3d)noneCorrect answer is option 'A'. Can you explain this answer?.
Solutions for What is the wrong statement?1) Complement of DFA that accepts those strings where after each ‘ a, always ‘ b ‘ appears, is the DFA that accepts those strings where after ‘ a ‘ never ‘ b ‘ appears.2) In a language – no. of state in minimal NFA is n, then in worst case, maximum no. of state in equivalent DFA is 2n.3) Minimal DFA always contains only one dead state.a)1b)1 & 2c)3d)noneCorrect answer is option 'A'. Can you explain this answer? in English & in Hindi are available as part of our courses for GATE.
Download more important topics, notes, lectures and mock test series for GATE Exam by signing up for free.
Here you can find the meaning of What is the wrong statement?1) Complement of DFA that accepts those strings where after each ‘ a, always ‘ b ‘ appears, is the DFA that accepts those strings where after ‘ a ‘ never ‘ b ‘ appears.2) In a language – no. of state in minimal NFA is n, then in worst case, maximum no. of state in equivalent DFA is 2n.3) Minimal DFA always contains only one dead state.a)1b)1 & 2c)3d)noneCorrect answer is option 'A'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of
What is the wrong statement?1) Complement of DFA that accepts those strings where after each ‘ a, always ‘ b ‘ appears, is the DFA that accepts those strings where after ‘ a ‘ never ‘ b ‘ appears.2) In a language – no. of state in minimal NFA is n, then in worst case, maximum no. of state in equivalent DFA is 2n.3) Minimal DFA always contains only one dead state.a)1b)1 & 2c)3d)noneCorrect answer is option 'A'. Can you explain this answer?, a detailed solution for What is the wrong statement?1) Complement of DFA that accepts those strings where after each ‘ a, always ‘ b ‘ appears, is the DFA that accepts those strings where after ‘ a ‘ never ‘ b ‘ appears.2) In a language – no. of state in minimal NFA is n, then in worst case, maximum no. of state in equivalent DFA is 2n.3) Minimal DFA always contains only one dead state.a)1b)1 & 2c)3d)noneCorrect answer is option 'A'. Can you explain this answer? has been provided alongside types of What is the wrong statement?1) Complement of DFA that accepts those strings where after each ‘ a, always ‘ b ‘ appears, is the DFA that accepts those strings where after ‘ a ‘ never ‘ b ‘ appears.2) In a language – no. of state in minimal NFA is n, then in worst case, maximum no. of state in equivalent DFA is 2n.3) Minimal DFA always contains only one dead state.a)1b)1 & 2c)3d)noneCorrect answer is option 'A'. Can you explain this answer? theory, EduRev gives you an
ample number of questions to practice What is the wrong statement?1) Complement of DFA that accepts those strings where after each ‘ a, always ‘ b ‘ appears, is the DFA that accepts those strings where after ‘ a ‘ never ‘ b ‘ appears.2) In a language – no. of state in minimal NFA is n, then in worst case, maximum no. of state in equivalent DFA is 2n.3) Minimal DFA always contains only one dead state.a)1b)1 & 2c)3d)noneCorrect answer is option 'A'. Can you explain this answer? tests, examples and also practice GATE tests.
|
|
Explore Courses for GATE exam
|
|
Suggested Free Tests
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
|
© EduRev
|
Education Revolution
|
|
Signup to see your scores
go up within 7 days!
Access 1000+ FREE Docs, Videos and Tests
Takes less than 10 seconds to signup