Question

1. If L is the complement of a language recognized by a non-deterministic finite automaton, then L is _______

a) finite

b) regular but not necessarily finite

c) deterministic context-free but not necessarily regular

d) context-free but not necessarily deterministic context-free

e) recursive (that is, decidable) but not necessarily context-free

f) recursively enumerable (that is, partially decidable) but not necessarily recursive

g) not recursively enumerable

Answer 1

Answer is as follows :

As we have L is complement of language recognized by NFA, we have to create it's DFA first. So it will be finite, context free but it can't be necessary to be deterministic context free., and sometimes it is decidable but not context free and not recursively enumerable because it is hard to work on turing machines.

So accordingly,

options A,D,E and G are correct.

if there is any query or wrong part ask in comments..