Just doing some work on Finite and infinite languages. And came across some statements I know the answer to but not sure how to explain why.

  1. There are finitely many finite languages. -This is false right? Since there are technically infinitely many finite languages

  2. Union of any two languages over alphabet (1,0) is regular. -False right? Since you can take a (non-reg U non-reg = non-reg)

  3. Single state NFA can recognize only finite languages -False, but I have no idea how to explain why...


1 Answer 1

  1. False. There are infinitely many finite language. Just think of {0,1}*. This is a infinite set of finitely long strings. or say, it is union of infinite number of finite languages over {0,1} which have strings of finite length.

  2. False. Union of two non regular languages MAY BE regular but it not the case always. This answer explains it well.

  3. False. Lets have a single state NFA having state q0. let 'd' be the transition function. d(q0, a) = q0 and since this is single state NFA, q0 is also final state. This NFA will accept all strings having only 'a'. i.e. {a,aa,aaa,aaaa...} The cardinality of this set is infinite, hence it can accept infinite languages too.

  • 1
    $\begingroup$ A union of two languages can be regular even if it is not the case that they are both regular. $\endgroup$ Commented Oct 10, 2019 at 23:04
  • $\begingroup$ @YuvalFilmus I have edited the second point. But I'm not sure if the first one is totally correct. Can you please have a look at it? $\endgroup$
    – Breakpoint
    Commented Oct 11, 2019 at 8:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.