<p><a href="https://mathoverflow.net/a/296879">As explained on MathOverflow by Damiano Mazza</a>, in some sense the <em>simply typed λ-calculus</em> 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.)</p>

CC BY-SA 4.0
2022-11-03T01:54:24.333Z
2022-11-03T01:54:24.333Z
Lê Thành Dũng 'Tito' Nguyễn
<p>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 <em>restrict</em> lambda calculus so it accepts only regular languages?</p>

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

CC BY-SA 3.0
2013-10-14T09:13:22.790Z
The question does make sense to some degree. The kinds of restrictions are based on "type systems".
Dave Clarke
CC BY-SA 3.0
2013-10-15T10:55:08.960Z
@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.
Martin Berger
CC BY-SA 3.0
2013-10-15T21:28:45.157Z
Good point. My question maybe should have been more general since this is one of the things I am curious about.
zpavlinovic
CC BY-SA 3.0
2013-10-16T10:48:24.653Z
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.
Martin Berger
CC BY-SA 3.0
2013-10-16T15:23:19.763Z
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.
zpavlinovic
<turing-machines><lambda-calculus><regular-language>
Regular languages in lambda calculus
zpavlinovic
# Regular languages in lambda calculus

(Asked by: username_0 on 2013-10-14)

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.

**Tags:** turing-machines, lambda-calculus, regular-language

> **Comments:**
> **username_1**: The question does make sense to some degree. The kinds of restrictions are based on "type systems".  
> **username_2**: @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.  
> **username_0**: Good point. My question maybe should have been more general since this is one of the things I am curious about.  
> **username_2**: 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.  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_3 on 2022-11-03. Score: 4

[As explained on MathOverflow by Damiano Mazza](https://mathoverflow.net/a/296879), 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.)


---

