Answer True or False. For either case, explain your answer. a) If an NFA accepts

Question

Answer True or False. For either case, explain your answer.

a) If an NFA accepts language (L), then an NFA that accepts the compliment of (L) can be constructed by making all the accept states non-accept states and vice-versa.

b) Is it not possible to have two topologically different DFAs that recognize the same language and have the same number of states.

c) A regular expression associated with a minimal DFA is unique.

d) Two strings are distinguishable by language L if a DFA recognizing L places them in different states.

e) The size of the largest set of strings that are pairwise distinguishable by language L is equal to the number of states in the minimal DFA that recognizes L.

f) All DFAs are deciders while not all NFAs are deciders.

Explanation / Answer

a) TRUE

an NFA accepts language (L), then an NFA that accepts the compliment of (L) can be constructed by making all the accept states non-accept states

b) FALSE

It is not a possibility to have 2 DFA with same Language with same number of states to acceppt same language

c) TRUE
THere is only one minimal DFAS for a regualr expression and viceversa

d) FALSE

Two strings are distinguishable by language L if a DFA recognizing L places them in different state is not possible

e) TRUE

f) TRUE

HOPE THIS HELPS
IF YOU FEEL ANY DOUBTS PLZZ COMMENT

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.