Префикс грамматикасы - Prefix grammar
Жылы теориялық информатика және ресми тіл теориясы, а грамматикалық префикс түрі болып табылады жолды қайта жазу жүйесі жиынтығынан тұрады жіп қайта жазу ережелер, және ұқсас ресми грамматика немесе а жартылай Thue жүйесі. Префикс грамматикасының ерекшелігі - олардың ережелерінің формасы емес, оларды қолдану тәсілі: тек префикстер қайта жазылған. Префикс грамматикасы бәрін сипаттайды қарапайым тілдер.[1]
Ресми анықтама
Префикс грамматикасы G Бұл 3 кортеж, (Σ, S, P), қайда
- Σ ақырлы алфавит
- S - бұл over -дан жоғары болатын негізгі жолдардың жиынтығы
- P форманың өндіріс ережелерінің ақырғы жиынтығы болып табылады сен → v қайда сен және v жолдар over
Жіптер үшін х, ж, біз жазамыз х →G ж (және айтыңыз: G шығара алады ж бастап х бір қадамда) егер жолдар болса u, v, w осындай , және v → w ішінде P. Ескертіп қой →G Бұл екілік қатынас Σ жіптерінде.
The тіл туралы G, деп белгіленді , -ден алынатын жолдар жиыны S нөлдік немесе одан да көп қадамдарда: формальды түрде жолдар жиынтығы w біреу үшін с жылы S, s R w, қайда R болып табылады өтпелі жабылу туралы →G.
Мысал
Префикс грамматикасы
- Σ = {0, 1}
- S = {01, 10}
- P = {0 → 010, 10 → 100}
арқылы анықталған тілді сипаттайды тұрақты өрнек
