Wolna encyklopedia

Symbol startowy to symbol nieterminalny wyróżniony w konkretnej gramatyce formalnej, taki że generację słowa w tej gramatyce zaczynamy od słowa złożonego z tego symbolu.

Jeśli chcemy zacząć generację od jakiegoś innego słowa w1, lub od pewnych kilku możliwych słów \{w_1,\dots,w_n\}, możemy dodać symbol "przedstartowy" S, oraz regułki postaci S\rightarrow w_i, o ile takie regułki mieszczą się w podzbiorze dozwolonych regułek dla danego typu gramatyk. Wystarcza nam więc jeden symbol startowy, niezależnie od tego, od ilu możliwych słów zamierzamy zaczynać.

Jest to możliwe dla wszystkich gramatyk od bezkontekstowych w górę. Nie zawsze jest to możliwe dla gramatyk regularnych oraz deterministycznych gramatyk bezkontekstowych.

Źródło: „haslo,Symbol_startowy”