Редовен граматика - тя
Създаване на набор от правила,
Редовен граматика може да се определи като съвкупност от правила, като ляв или десен редовен граматиката.
прав редовен граматика - всички правила могат да бъдат в една от следните форми:
лявото редовен граматика - всички правила могат да бъдат в една от следните форми:
- капачки (А. В) означават не-терминали от множеството N
- малки букви (а. б) означават терминали от множеството Σ
- ε - празен низ, т.е. дължина линия 0
Класове на десните и леви редовни граматики са еквивалентни - индивидуално достатъчни, за да се определят всички редовни езици. Всеки редовен граматика могат да бъдат превърнати от ляво на дясно и обратно.
Дясната редовен граматиката Г. предварително определен N =, Σ =, P се състои от следните правила:
S → като S → ба → ε А → сА
и S е символ за старт. Тази граматика описва същия език, на регулярния израз на * * ж.к..
ограниченост
Всеки контекст без граматика може лесно да се преобразува във форма, в която правилата състоят само от лявата редовен и десния редовни (за контекст без граматики се оставя присъствието на двете едновременно). Следователно такива граматики могат да изразят всички контекстно-свободен език. Редовни граматики може да има или ляво-редовно правила или десен редовно, но не и двете едновременно. Поради това, те могат да се опишат с ограничена подгрупа от езици, наречени редовни езици.
Например, контекстно-свободен език струни aibi тип определено граматика Г., където N =, Σ =, P се състои от правила
S → Аа → Sb S → ε
и S е символ за старт. Имайте предвид, че тази граматика съдържа както леви-редовни и десния редовни правила и поради това не е редовен.
литература
Вижте какво е "редовен граматика" в други речници:
Чомски йерархия - Чомски йерархия класификация на официалните езици и формални граматики, според която те се разделят на 4 типа според тяхната условно сложност. Предложен от професор MIT лингвист Ноам Чомски. ... ... Wikipedia
Редовен граматика - по компютърни науки, редовно граматика е официална граматика от типа 3 от Чомски йерархия. Редовни граматики се даде точно определение на всички редовни езици, и по тази причина се равнява на крайни автомати и регулярни изрази. Редовни граматики ... ... Wikipedia
Граматика официално - формална граматика и граматика в официалната теория език начин за описване на формален език, т.е. разпределението на подмножество на множеството на всички думи на краен alfavita. Разграничаване генериране и разпознаване (или ... ... Wikipedia
Тюринг пълнота - В изчислимост теория изпълнител (множество изчислените членове) е Тюринг пълно, ако е възможно да се осъществи всеки изчислима функция. С други думи, за всеки съществува изчислима функция изчислява своя елемент (например ... ... Wikipedia
- Стохастична контекст без граматика. Dzhessi Rassel. Тази книга ще бъде направено в съответствие с вашата поръчка на технологии технология за печат при поискване. Високо качество на съдържанието от статиите в Уикипедия! Стохастична контекст без граматика (SCS, ... Прочети повече Купи за 854 рубли
- Тъй като съм учи език. Бележки полиглот. Lomb Kato. Kato Lomb, който знае 16 езика, като се смята, че разделянето на хората в и тези с "специални езикови способности" погрешно. Тази книга - квинтесенцията на опита си, отражения isovety полиглот: ... Прочетете повече Купи за 743 рубли
- Тъй като съм учи език. Бележки полиглот. Lomb К. Тази книга - ярък и директна експозиция на мнения се говореха и един от първите тълкуватели на света по различни езикови системи. В основата на тази books- собствен учебен опит ... Прочетете още Купи за 599 рубли