Symbol startowy


Symbol startowy w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

Symbol startowysymbol 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 w 1 , {\displaystyle w_{1},} lub od pewnych kilku możliwych słów { w 1 , , w n } , {\displaystyle \{w_{1},\dots ,w_{n}\},} możemy dodać symbol „przedstartowy” S , {\displaystyle S,} oraz reguły przepisywania (zwane też produkcjami) postaci S w i , {\displaystyle S\to w_{i},} o ile takie reguły mieszczą się w podzbiorze dozwolonych produkcji dla danego typu gramatyk. Wystarcza nam więc jeden symbol startowy, niezależnie od tego, od ilu możliwych słów zamierzamy zaczynać.

Nie zawsze jest to jednak możliwe, zwłaszcza dla gramatyk regularnych oraz deterministycznych gramatyk bezkontekstowych.

Na podstawie artykułu: "Symbol startowy" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy