редовен граматика

Създаване на набор от правила,

Редовен граматика може да се определи като съвкупност от правила, като ляв или десен редовен граматиката.

прав редовен граматика - всички правила могат да бъдат в една от следните форми:

лявото редовен граматика - всички правила могат да бъдат в една от следните форми:

• капачки (А. В) означават не-терминали от множеството N
• малки букви (а. б) означават терминали от множеството Σ
• ε - празен низ, т.е. дължина линия 0

Класове на десните и леви редовни граматики са еквивалентни - индивидуално достатъчни, за да се определят всички редовни езици. Всеки редовен граматика могат да бъдат превърнати от ляво на дясно и обратно.

Дясната редовен граматиката Г. предварително определен N =, Σ =, P се състои от следните правила:

S → като S → ба → ε А → сА

и S е символ за старт. Тази граматика описва същия език, на регулярния израз на * * ж.к..

Всеки контекст без граматика лесно могат да бъдат превърнати във форма, в която са направени правилата съставена само от лявата и дясната редовен-редовно (за контекстно-свободни граматики се допуска присъствието на двамата по едно и също време). Следователно такива граматики могат да изразят всички контекстно-свободен език. Редовни граматики може да има или ляво-редовно правила или десен редовно, но не и двете едновременно. Поради това, те могат да се опишат само част от езици, наречени редовни езици.

Например, контекстно-свободен език нанизи от формата на а н и. i≥0 дефинирани граматика G. където N =, = Σ, Р състои от правила

S → Аа → Sb S → ε

и S е символ за старт. Имайте предвид, че тази граматика съдържа както леви-редовни и десния редовни правила и поради това не е редовен.