3
$\begingroup$

I was looking at this picture: https://upload.wikimedia.org/wikipedia/commons/thumb/a/a2/Automata_theory.svg/640px-Automata_theory.svg.png

Which made me think, that if all Turing Machines PDA's and FSA's recognize certain sets of languages, there has to be a set of languages which is recognized by Combinational Logic circuits.

A quick look around on this site and on wikipedia has led me to believe that circuits cannot recognize languages because theyre stateless but I want to hear that preferably from someone who knows more than me in this subject.

| cite | improve this question | |
$\endgroup$
  • 3
    $\begingroup$ I'm not sure what combinational logic is, but if it refers to circuit, then they are a very different type of computation model, since they operate on inputs of fixed length. $\endgroup$ – Yuval Filmus Aug 2 '17 at 17:46
  • $\begingroup$ en.wikipedia.org/wiki/Circuit_complexity $\endgroup$ – D.W.♦ Aug 2 '17 at 18:02
  • $\begingroup$ I was thinking more in the direction of stateless computation: en.wikipedia.org/wiki/Sequential_logic vs. en.wikipedia.org/wiki/Combinational_logic $\endgroup$ – zython Aug 2 '17 at 19:19
  • 1
    $\begingroup$ It is not what I would call part of "automata theory". I have been wondering too, but was too lazy to remove the figure. Or paerhaps better, I am to lazy to handle the resulting yes/no battles. $\endgroup$ – Hendrik Jan Aug 2 '17 at 19:41
  • $\begingroup$ @D.W. You are right. But then it makes no sense to draw the class inside regular languages. $\endgroup$ – Hendrik Jan Aug 3 '17 at 7:24

Your Answer

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

Browse other questions tagged or ask your own question.