حل تمرین نظریه محاسبات/فصل چهارم/حل تمرین ۴-۱۴

برای اینکه نشان دهیم A تصمیم پذیر است کافی است یک گرامر منظم برای آن ارایه دهیم و یا یک ماشین NFA یا PDA برای آن ارایه دهیم.

Regular Grammer :
S -> x111x
x -> 0x | 1x | λ