فرض کنید زبان L شامل فقط سه تا دستور زیر باشد:
دستور اضافه کردن =
A=A+1
دستور کم کردن=
A=A-1
دستور شرطی =
IF A!=0 GOTO B
که B یک Label است.
(کل دستورات زبان همیناست)
قدرت ماشین تورینگ و زبان ساده ی L معادل است. توضیح دهید در زبان L چه محدودیت هایی ایجاد کنیم تا قدرت آن معادل باشد با ماشین تورینگی که طول نوار آن محدود به طول ورودی است ( LBA )
Гілка فرض کنید زبان L شامل فقط سه تا دستور زیر باشد:
3 повідомлення · –В В