9
$\begingroup$

With Turing machines, by imposing certain restrictions on the form of the transition function, one can get a machine that accepts only regular languages. I am wondering what is the counterpart in lambda calculus? In other words, how to restrict lambda calculus so it accepts only regular languages?

Related papers would be great, just as an explanation if my question does not make any sense, if that is the case.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ The question does make sense to some degree. The kinds of restrictions are based on "type systems". $\endgroup$
    – Dave Clarke
    Oct 14, 2013 at 9:13
  • 1
    $\begingroup$ @bellpeace What alphabet are the languages over, what does acceptance mean in this context? After all, the input and output of $\lambda$-terms are themselves $\lambda$-terms. Regular languages are strings over an alphabet, but without encoding or extensions, $\lambda$-calculus does not feature strings. $\endgroup$
    – Martin Berger
    Oct 15, 2013 at 10:55
  • $\begingroup$ Good point. My question maybe should have been more general since this is one of the things I am curious about. $\endgroup$
    – zpavlinovic
    Oct 15, 2013 at 21:28
  • $\begingroup$ The standard definition of regular languages does not take into account the internal structure of elements of the alphabet. That's fine, but if you have something like $\lambda$-terms with a lot of interesting internal structure, you'd probably want to think about how to combine regularity with that internal structure. Have you got a specific application in mind? That could give you some ideas about what properties could be interesting here. $\endgroup$
    – Martin Berger
    Oct 16, 2013 at 10:48
  • $\begingroup$ Since untyped $\lambda$ calculus is Turing-complete, I was mainly interested in how to look at Chomsky hierarchy through the lense of lambda calculus. There is no specific application, yet merely theoretical interest. $\endgroup$
    – zpavlinovic
    Oct 16, 2013 at 15:23

1 Answer 1

Reset to default
3
$\begingroup$

As explained on MathOverflow by Damiano Mazza, in some sense the simply typed λ-calculus captures exactly the regular languages. (It is unclear however whether there is anything interesting to be said about the rest of the Chomsky hierarchy in this context.)

Improve this answer
$\endgroup$

Your Answer

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

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