4
$\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.

$\endgroup$
6
  • 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$ Aug 2, 2017 at 17:46
  • $\begingroup$ en.wikipedia.org/wiki/Circuit_complexity $\endgroup$
    – D.W.
    Aug 2, 2017 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, 2017 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$ Aug 2, 2017 at 19:41
  • $\begingroup$ @D.W. You are right. But then it makes no sense to draw the class inside regular languages. $\endgroup$ Aug 3, 2017 at 7:24

1 Answer 1

1
$\begingroup$

Yes IF we accept some restrictions regarding the fixed size of the input, and we consider the outputs to be part of the domain of discourse appended at the end of the input (or, for single-bit outputs, use it as an indicator of valid inputs).

There is a mapping betweeen types of grammar and the type of automaton that can recognise them:

Type    Grammar Accepted          Automaton
Type 0  Unrestricted grammar      Turing Machine
Type 1  Context-sensitive grammar Linear-bounded automaton
Type 2  Context-free grammar      Pushdown automaton
Type 3  Regular grammar           Finite state automaton

One one hand, we can always build a finite state automaton that accepts the same set of valid inputs, arriving at the same final state / output, as any given combinational circuit.

Inversely, the set of valid inputs for a combinational circuit does define a language which is produced by a grammar, and a regular (type 3) grammar is guaranteed to be enough to generate that language (albeit it may not be the best approach to model a given combinational circuit, and the complexity and semantics of the resulting grammar may be no better than a huge input/output table).

Let's think, for example, of a circuit that validates a parity bit for a given byte, with a 9-bit input: you could say that such combinational circuit implements a grammar, and the produced language is the set of bytes with correct parity bits.

Again, in many applications of combinational logic, however, thinking in terms of formal languages theory is not the most useful approach (since their input is limited, we often think in terms of truth tables and boolean logic).

This answer provides further insights: What is the connection between combinatorial circuits and finite state automata?

$\endgroup$
2
  • $\begingroup$ It's been quite some time since I studied this, corrections and reviewals are very welcome. $\endgroup$
    – jjmontes
    Nov 11, 2022 at 6:47
  • $\begingroup$ (A combinational circuit has a fixed size input.) $\endgroup$
    – greybeard
    Nov 11, 2022 at 7:58

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.