Пусть <tex>p</tex> разрешает <tex>L_1</tex>, а <tex>q</tex> разрешает <tex>L_2</tex>.
1. * Построим программу <tex>r</tex>, разрешающую <tex>L_1\cap L_2</tex>: <tex>r(x):\colon</tex> '''return''' <tex>p(x) </tex> '''and''' <tex>q(x)</tex>2. * Построим программу <tex>r</tex>, разрешающую <tex>L_1\cup L_2</tex>: <tex>r(x):\colon</tex> '''return''' <tex>p(x) </tex> '''or''' <tex>q(x) </tex>3. * Построим программу <tex>r</tex>, разрешающую <tex>L_1L_2</tex>: <tex>r(x):\colon</tex> n = <tex>n = |</tex>x<tex>|</tex> mid =<suptex>mid \gets?</sup> \ \{1 .. \mathinner{\ldotp\ldotp} n\}</tex> '''return''' <tex>p(x[1 .. \mathinner{\ldotp\ldotp} mid]) </tex> '''and''' <tex>q(x[mid+1 .. \mathinner{\ldotp\ldotp} n])</tex>4. * Построим программу <tex>r</tex>, разрешающую <tex>L_1^*</tex>:
<code>
<tex>r(x):\colon</tex> n = <tex>n = |x|</tex>x <tex>|prev = 1</tex> prev = 1
'''do'''
cur =<suptex>cur \gets?</sup> \ \{prev .. \mathinner{\ldotp\ldotp} n\}</tex> '''if not''' <tex>p(x[prev .. \mathinner{\ldotp\ldotp} cur])</tex>
'''return''' ''false''
<tex>prev = cur + 1</tex> '''while''' <tex>cur != \ne n</tex>
'''return''' ''true''
</code>
