Формальні мови та їх завдання, Детальна інформація

Є два види граматик з продукціями обмеженого вигляду, якими задаються регулярні мови, – це праволінійні та ліволінійні граматики. Праволінійною (ліволінійною) називається граматика, всі продукції якої мають вигляд A\xF0AE w або A\xF0AE wB (відповідно, A\xF0AE w або A\xF0AE Bw), де A, B – нетермінали, w\xF0CE X*. Усі можливі праволінійні та ліволінійні граматики з термінальним алфавітом X породжують в точності клас регулярних мов над X. Це доводиться, наприклад, в [АУ].