– zaznaczony symbol wędruje w prawo

– i na końcu zmienia się w symbol terminalny, któremu odpowiada. Pozwalamy co prawda -owi zmienić się szybciej, ale wtedy żaden z -ów na prawo od niego nigdy nie zamieni się w symbol terminalny, więc reguła ta de facto może być użyta tylko kiedy nie ma już żadnych nieterminali na prawo od zmienianego. Kiedy całe słowo przejdzie już na prawo, będziemy mieli słowo postaci

– po wykonaniu całej pracy zmienia się w zwykłe

Przykładowe wyprowadzenie:

Przykład (2) Przykładem języka kontekstowego, który nie jest bezkontekstowy jest zbiór słów L = { gdzie n jest liczbą pierwszą}

Przypisy

Kategoria:Języki formalne