fy"> за один крок виведена ланцюжок (кажуть також
безпосередньо виведена ). Це відношення позначається G . Ставлення
виводимості за 0 або більше кроків позначається G * (рефлексивно-транзитивне замикання відносини G ) і називається просто
ставленням виводимості . Послідовність ланцюжків називається
висновком довжини n 0. Висновок також будемо позначати іноді G * . У разі, коли зрозуміло, в якій граматиці розглядається висновок, індекс G можна опускати.
Мовою , породжуваним граматикою G називається безліч термінальних ланцюжків, що виводяться з S , тобто безліч L ( G ) = {| T * , S * }. Клас мов, породжуваних граматиками загального вигляду називається класом мов типу 0 .
Контекстно-залежною (або типу 1 ) називається граматика з правилами виду. Завдяки цьому нерівності ці граматики називаються ще неукорачівающімі . Мова, породжуваний контекстно-залежної граматикою, називається також контекстно-залежним (або типу 1 ). Очевидно, що така мова не містить.
КС-граматикою (або контекстно-вільною граматикою і граматикою типу 2 ) називається граматика з правилами виду A , де
