I passed by this question in a previous exam while studying for the "Automata / Theory Of Computation" and I am struggling to find answer. I would appreciate it if someone can help me with it:

This is the question:

a)On the basis of what was covered in class, draw the Venn diagram representing the following sets:

1.REXP: the set of the language given by all regular expressions

2.DFSA: the set of all languages recognized by deterministic FSAs

3.NFSA: the set of all languages recognized by non-deterministic FSAs

4.CFG: the set of all languages generated by context free grammars

5.PDA: the set of all languages recognized by PDAs

  • 3
    $\begingroup$ Welcome to the site! We'd be happy to help you, but you have to help us first, by answering some other questions. For instance: What's giving you problems? What parts of the question can you answer immediately? What don't you understand? and so on. $\endgroup$ Jan 11, 2020 at 14:28
  • 1
    $\begingroup$ I suspect the difficulty is with the term Venn diagram. $\endgroup$ Jan 11, 2020 at 20:29

1 Answer 1


The relevant set-theoritic relations are $$ \mathsf{REXP} = \mathsf{DFSA} = \mathsf{NFSA} \subsetneq \mathsf{CFG} = \mathsf{PDA}. $$ The corresponding Venn diagram consists of two circles, one inside the other.


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.