0
$\begingroup$

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

$\endgroup$
  • 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$ – Rick Decker Jan 11 at 14:28
  • 1
    $\begingroup$ I suspect the difficulty is with the term Venn diagram. $\endgroup$ – Yuval Filmus Jan 11 at 20:29
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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