Please ignore the answers i\'ve checked because I don\'t not think they\'re righ
ID: 3786939 • Letter: P
Question
Please ignore the answers i've checked because I don't not think they're right. Also please give brief reasoning for why something is T/F too!
QUESTION 1 For any regular language there is an NFA with exactly 1 final state with language L. o True False When an NFA M s converted to a DFA M only adding states as needed M' may have more states than M does True False When an NFA s converted to a DFA M only adding states as needed M' may have the same number of states as M True O False When an NFA M is converted to a DFA M', only adding states as needed, M' may have fewer states than M does True O FalseExplanation / Answer
1.True.
For each atomic form of regular expression, a (a ), , and , we give an NFA accepting just the strings matching that regular expression
By definition of Regular Language.
A language is regular iff it is the set of strings accepted by some deterministic finite automaton.and every DFA is NFA.
2.True.
A Deterministic finite automaton (DFA) is a special kind of NFA, in which for each state and alphabet, the transition function has exactly one state. Thus clearly every formal language that can be recognized by a DFA can be recognized by an NFA.
Conversely, for each NFA, there is a DFA such that both recognize the same formal language. The DFA can be constructed using the powerset construction.
if the NFA has n states, the resulting DFA may have up to 2^n states--this makes the other next questions statements as false