Select all the statements below which are true: c) A language accepted by some d
ID: 3887122 • Letter: S
Question
Select all the statements below which are true:
c) A language accepted by some dfa is a regular language and a language accepted by some nfa is a nonregular language.
e) There are languages accepted by dfa's which cannot be accepted by nfa's.
f) Transition function of a dfa can be defined using a transition table.
b) Let . Let M be a dfa and let be the corresponding transition graph. Let m be the number of vertices in . Then .
c) A language accepted by some dfa is a regular language and a language accepted by some nfa is a nonregular language.
d) Let and q0 be the initial state of a dfa M. Then the transition graph of M has 3 outgoing edges in q0.
e) There are languages accepted by dfa's which cannot be accepted by nfa's.
f) Transition function of a dfa can be defined using a transition table.
= {a, b, c}Explanation / Answer
In the given statements , the statements (a) , ,(b), (d) and (f) are true .
(a) Let = {a,b,c } ad M be a nfa . Let qi be a state of M , Then (qi ,a ) * (qi , a ) , the statement is true because the extended transition function * contains all the or few elements of transition function .
(b) Let = { a1 , a2 ,.... an} Let M be a dfa and let Gm be the corresponding transition graph. Let m be the number of vertices in Gm Then m>= n . The statement is true because the number of vertices in transition graph can be more than the input alphabets and the number of vertices are exactly equal to the number of states .
(d) The statement , Let = {0,1,2 } and q0 be the initial state of a dfa M. Then the transition graph of M has 3 outgoing edges in q0 is also true because each vertex must have exactly same || number of outgoing edges , which is to be labelled with different element of .
(f) The transition table defines the transition function of a dfa , It takes arguments as the input and returns a state , which can be represented as state (q, a). where q is the state corresponding to the input a . Hence the statement is true.
The statements (c) and (e) are false.
(c) A language accepted by some dfa is a regular language and a language accepted by some nfa is a nonregular language. This statement is false because according to the conversion theorem a language which is accepted by a nfa with transitions is also accepted by dfa hence , a language accepted by nfa with or without transitions is regular.
(e) There are languages accepted by dfa's which cannot be accepted by nfa's. This statement is false because according to the theorem , A language L is accepted by a DFA if and only if there is an NFA N such that L(N) = L.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.