(g) If there is an NFA with s states which accepts a language L, then we can con
ID: 3594071 • Letter: #
Question
(g) If there is an NFA with s states which accepts a language L, then we can construct a DFA which accepts the same language and has: (circle the smallest correct answer a) s states b) 2s states d) 2 states (h) If there is a DFA which accepts a language A with s states and another whiclh accepts language B with t states, then we can construct a DFA which accepts An B which has (circle the smallest correct answer) a) s t states b) st states c) (st)2 d) 2+ states CSC320 SO1 Page 2 (i) Let M be a DFA. There is an algorithm to test if L(M)0in time linear in the T F number of states and transitions of M (i) The language accepted by a PDA (pushdown automata) with a finite stack is T F regular Explain your answerExplanation / Answer
g) If NFA has s states, then DFA accepts the same language with 2s states. Hece option d is the right answer.
h) AB will have s+t states. Hence option a is the answer.
i) True, there is an efficient (linear time) algorithm that, given a DFA with -transitions M, decides whether L(M) = .
j)True. With only finite positions in stack, we can have only finite configurations and these can also be modeled as states in a finite automata.PDA is equivalent to DFA with a finite stack.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.