Энгийн хэл ба хязгаарлагдмал төлөвт машинууд. Хязгаарлагдмал автомат ба ердийн хэлүүд Даммигийн албан ёсны хэлний онол

Бид хэлийг нэгтгэх үйлдлүүдийг мэддэг. Холболтын болон давталтын үйлдлүүдийг тодорхойлъё (заримдаа Kleene хаах гэж нэрлэдэг).

L 1 ба L 2 нь цагаан толгойн хэлээр байг

Дараа нь, өөрөөр хэлбэл. хэлний холболтЭхний хэлний бүх үгсийг хоёр дахь хэлний бүх үгстэй холбохоос бүрдэнэ. Тодруулбал, хэрэв , тэгвэл , хэрэв , тэгвэл .

L хэлний "зэрэг"-ийн тэмдэглэгээг танилцуулъя:

Ийнхүү L i-д L-ээс i дараалсан үгэнд хуваагдаж болох бүх үгс багтана.

L хэлний давталт (L) * нь L хэлнээс хэд хэдэн дараалсан үг болгон хувааж болох бүх үгсээр үүсгэгддэг.

Үүнийг градус ашиглан илэрхийлж болно:

Энэ хэлэнд байхгүй бол хоосон үг агуулаагүй хэлний "тасарсан" давталтыг авч үзэх нь ихэвчлэн тохиромжтой байдаг: . Энэ бол шинэ үйлдэл биш, зүгээр л илэрхийлэлд тохиромжтой товчлол юм.

Хэрэв бид цагаан толгойг нэг үсэгтэй үгсээс бүрдэх хязгаарлагдмал хэл гэж үзвэл цагаан толгойн бүх үгс, түүний дотор хоосон үгсийн багцыг өмнө нь оруулсан тэмдэглэгээ нь энэ хэлний давталтын тодорхойлолттой тохирч байгааг анхаарна уу.

Дараах хүснэгтэд албан ёсны индуктив тодорхойлолтыг өгсөн болно тогтмол илэрхийллүүдцагаан толгой, тэдгээрийн төлөөлдөг хэл дээр.

Илэрхийлэл r	Хэл L r
	L a =(a)
r 1 ба r 2 байг	L r1 ба L r2 - төлөөлөх боломжтой
тогтмол илэрхийллүүд.	тэдний хэл.
Дараа нь дараах илэрхийллүүд
тогтмол байдаг	болон хэлийг төлөөлнө:
r=(r 1 +r 2)
r=(r 1 тойрог 2)
r=(r 1) *	L r =L r1 *

Бичлэг хийх үед тогтмол илэрхийллүүдБид залгах тэмдгийг орхиж, * үйлдлийг холбох ба +-ээс илүү давуу эрхтэй гэж үзнэ, холболт нь + -ээс илүү давуу эрхтэй гэж үзнэ. Энэ нь олон хашилтыг орхих боломжийг олгоно. Жишээлбэл, 10(1 * + 0) гэж бичиж болно.

Тодорхойлолт 5.1. Хоёр тогтмол илэрхийллүүдХэрэв тэдгээрийн төлөөлж буй хэл нь ижил байвал r ба p нь тэнцүү гэж хэлнэ, өөрөөр хэлбэл. L r = L p. Энэ тохиолдолд бид r = p гэж бичнэ.

Жишээ нь дараахь зүйлийг шалгахад хялбар байдаг тогтмол шинж чанаруудүйл ажиллагаа:

• r + p= p+ r (холбооны шилжих чадвар),
• (r+p) +q = r + (p+q) (холбооны холбоо),
• (r p) q = r (p q) (холбооны холбоо),
• (r *) * = r * (давталтын чадвар),
• (r +p) q = rq + pq(тараах чадвар).

Жишээ 5.1. Тийм ч тодорхой бус тэгш байдлыг жишээ болгон баталъя: (r + p) * = (r * p *) *.

L 1 хэлийг зүүн талаас нь, L 2-ыг баруун талаас нь илэрхийлнэ. Хоосон үг нь хоёр хэлэнд хамаарна. Хэрэв үг нь хоосон биш бол давталтын тодорхойлолтоор тухайн хэлэнд хамаарах дэд үгсийн холболтоор илэрхийлж болно. Гэхдээ энэ хэл нь L"=L r * L p * (яагаад?) хэлний дэд хэсэг юм. Тиймээс . Эсрэгээр, хэрэв үг бол , дараа нь энэ нь L " хэлэнд хамаарах дэд үгсийн холболтоор илэрхийлэгддэг. Ийм дэд үг бүр v хэлбэрээр илэрхийлэгддэг. v= v 1 1 ... v k 1 v 1 2 ... v l 2

, энд бүх i=1, ... , k нь дэд үг бөгөөд бүх j=1, ... , l нь дэд үг (k эсвэл l нь 0-тэй тэнцүү байх боломжтой). Гэхдээ энэ нь w нь дэд үгсийн нэгдэл бөгөөд тус бүр нь -д харьяалагддаг гэсэн үг юм.

Ердийн хэл Хэлний онолдердийн багц (эсвэл,ердийн хэлээр

) дараах шинж чанаруудыг хангасан албан ёсны хэл гэж нэрлэдэг. Эдгээр энгийн шинж чанарууд нь ердийн багцын ангиллыг бүхэлд нь судлахад тохиромжтой бөгөөд олж авсан үр дүн нь албан ёсны хэлний олон чухал тохиолдлуудад хэрэглэгдэх боломжтой юм. Өөрөөр хэлбэл ердийн олонлогийн тухай ойлголт нь математик бүтцийн жишээ юм.

Ердийн багцын тодорхойлолт Σ нь хязгаарлагдмал цагаан толгой байг.Ердийн багц

№.	Σ цагаан толгойн R(Σ) нь дараах рекурсив шинж чанаруудаар тодорхойлогддог.	Өмч
1		Тодорхойлолт
2		Хоосон багц нь Σ цагаан толгойн ердийн олонлог юм
3		Зөвхөн нэг хоосон мөрөөс бүрдэх олонлог нь Σ цагаан толгойн ердийн олонлог юм
4		Σ цагаан толгойн аль нэг тэмдэгээс бүрдэх олонлог нь Σ цагаан толгойн ердийн олонлог юм.
5		Хэрэв аль нэг хоёр багц Σ цагаан толгойн үсгээр тогтмол байвал тэдгээрийн нэгдэл нь Σ цагаан толгойн ердийн олонлог болно.
6		Хэрэв аль нэг хоёр олонлог Σ цагаан толгойн үсгээр тогтмол байвал тэдгээрийн элементүүдийн бүх боломжит хослолуудаас бүрдэх олонлог нь Σ цагаан толгойн ердийн олонлог болно.
		Хэрэв ямар нэгэн олонлог Σ цагаан толгойн үсгээр тогтмол байвал түүний элементүүдийн бүх боломжит хослолын багц нь мөн цагаан толгойн Σ үсгийн ердийн олонлог болно.

Дараахаас өөр зүйл бол Σ цагаан толгойн ердийн олонлог биш юм

• Мөн үзнэ үү

Автомат арга дээр үндэслэн задлан шинжлэгчийг бүтээх

Викимедиа сан.

2010 он.Бусад толь бичигт "Ердийн хэл" гэж юу болохыг харна уу: ердийн хэл

- (Латин Regulaius, зохицуулалтын дүрэм гэсэн үг). Зөв, зөв ​​зохион байгуулсан, хийсэн. Машиныг тогтмол ажиллуулах. Тэр ч байтугай цус харвалт. Тогтмол амьдрал. Зөв, зохистой, нэгэн хэвийн амьдрал. Орос хэлэнд орсон гадаад үгсийн толь бичиг....... ... Орос хэлний гадаад үгсийн толь бичиг

см… Синонимын толь бичиг

Эртний бичгийн хэл- Удаан хугацааны бичгийн уламжлалтай хэл, өөрөөр хэлбэл хэдэн зууны өмнө тухайн хэлний бүтцэд тохирсон бичгийн хэлийг хүлээн авсан бөгөөд хэлний бичгийн хувилбарын үйл ажиллагаа нь үечилсэн бус, тогтмол, ... . .. Нийгэм хэл шинжлэлийн нэр томъёоны толь бичиг

Энэ нэр томъёо нь өөр утгатай, Кечуа хэлийг үзнэ үү. Кечуа нэр: Кхичва Сими, Руна Сими улсууд ... Википедиа

Ижил хэмжээтэй (болгар; Български) жигд араг яс (чех; Čeština) pravidelný араг яс (Герман; Deutsch) regelmäßiges Skelett (Унгар; Мажар) szabályos... ... Барилгын толь бичиг

- [ФРАНЦ PARK] геометрийн тогтмол зохион байгуулалттай цэцэрлэгт хүрээлэн, ихэвчлэн тэнхлэгийн байрлалтай (болгар; Български) frenski park (Чех; Čeština) francouzsky park (Герман; Deutsch) regelmäßiger Park; Францезишер цэцэрлэгт хүрээлэн…… Барилгын толь бичиг

Кечуа Өөрийн нэр: Кхичва Сими, Руна Сими Улс: Аргентин, Болив, Колумб, Перу, Чили, Эквадор Бүс нутаг: Андын нуруу Албан ёсны статус: Перу ... Википедиа

Тагалог хэл- (тагал, тагала, тагало; тагалог) Филиппин хэлний нэг. Анхны тархалтын нутаг дэвсгэр нь Бүгд Найрамдах Филиппин Улсын улс төр, эдийн засаг, соёлын хувьд хамгийн чухал бүс нутаг болох арлын төв ба өмнөд хэсэгт оршдог... ... Хэл шинжлэлийн нэвтэрхий толь бичиг

Номууд

• Үүсмэл үйл үг. Финляндын дүрмийн нууцууд. Сурах бичиг, Сафронов В.Д. Энэхүү гарын авлага нь орос хэлний боловсролын уран зохиол дахь Финлянд хэлний дүрмийн хамгийн сонирхолтой, хангалтгүй танилцуулсан хэсгүүдийн нэг болох үүсмэл үйл үгүүдэд зориулагдсан болно. Тэдгээр нь үйл үг, нэрнээс бүрддэг ...

Тогтмол дүрэм, хязгаарлагдмал автомат ба ердийн олонлогууд (мөн тэдгээрийг төлөөлөх тогтмол хэллэгүүд) нь ердийн хэлийг тодорхойлох гурван өөр арга юм.

Мэдэгдэл

Хэл нь зөвхөн зүүн-шугаман (баруун-шугаман) дүрмээр тодорхойлогдсон тохиолдолд PM болно. Хэл нь ердийн багц бол зөвхөн зүүн шугаман (баруун-шугаман) дүрмээр тодорхойлогддог.

Хэл нь хязгаарлагдмал төлөвийн машинаар тодорхойлогдсон тохиолдолд л РМ болно. Хэл бол PM байх тохиолдолд л төрийн машинд танигдана.

Эдгээр гурван арга бүгд тэнцүү байна. Эдгээр аргуудын аль нэгээр тодорхойлогдсон хэлний хувьд ижил хэлийг тодорхойлсон өөр аргыг бий болгох боломжийг олгодог алгоритмууд байдаг. Эдгээр алгоритмуудын нарийвчилсан тайлбарыг уран зохиолоос авах боломжтой (жагсаалтыг харна уу).

Жишээлбэл, зөв ​​шугаман дүрмээр тодорхойлогдсон хэлний тогтмол илэрхийллийг олохын тулд тогтмол коэффициент бүхий тэгшитгэлийн системийг байгуулж, шийдвэрлэх шаардлагатай.

Програмчлалын хэлний онолд хамгийн чухал үүрэг нь CA ба ердийн дүрмийн дүйцэх чадвар юм, учир нь ийм дүрмийг програмчлалын хэлний лексик бүтцийг тодорхойлоход ашигладаг. Мэдэгдэж буй дүрмийн дагуу автомат машин үүсгэсний дараа бид тухайн хэлний танигчийг олж авдаг. Ингэснээр тухайн хэлний үгийн сангийн бүтцийг задлан задлах асуудлыг шийдвэрлэх боломжтой.

Мэдэгдэж буй ердийн дүрмийн үндсэн дээр CA-г бүтээхийн тулд үүнийг автомат хэлбэрт оруулах ёстой. Автоматын төлөвийн багц нь дүрмийн төгсгөлийн бус тэмдэгтүүдийн багцтай тохирч байх болно. 2.3.2 Энгийн хэлний шинж чанарууд

Хэрэв энэ үйлдлийг түүний аль нэг элемент дээр гүйцэтгэсний үр дүнд ижил олонлогт хамаарах шинэ элемент гарч ирвэл олонлогийг зарим үйлдлийн дагуу хаалттай гэж нэрлэдэг.

Энгийн олонлогууд нь огтлолцох, нэгдэх, нэмэх, давтах, холбох, тэмдэгтийн нэрийг өөрчлөх, тэмдэгт мөрийг орлуулах үйлдлүүдийн дор хаагддаг.

Ердийн хэлнүүдийн хувьд бусад төрлийн хэлээр шийдэгдэх боломжгүй олон асуудлыг шийдэж болно. Жишээлбэл, хэлийг ямар хэлбэрээр зааж байгаагаас үл хамааран дараахь асуудлуудыг шийдвэрлэх боломжтой.

Тэнцвэртэй байдлын асуудал: L 1 (V) ба L 2 (V) гэсэн хоёр энгийн хэлийг өгсөн. Тэдгээр нь тэнцүү эсэхийг тодорхойлох шаардлагатай.

Хэлний гинжин хэлхээний асуудал. Энгийн хэлний L(V) өгөгдсөн V * тэмдэгтийн мөр. Энэ хэлхээ хэлэнд хамаарах эсэхийг шалгах хэрэгтэй.

Хэлний хоосон байдлын асуудал. Энгийн хэл L(V) өгөгдсөн. Энэ хэл хоосон эсэхийг шалгах шаардлагатай, i.e. ядаж нэг гинжийг олоорой, L(V).

Заримдаа тодорхой хэл тогтмол байдаг эсэхийг батлах шаардлагатай байдаг. Хэрэв энэ хэлийг авч үзсэн аргуудын аль нэгээр нь зааж өгөх боломжтой бол энэ нь тогтмол байна. Гэхдээ ийм арга олдохгүй бол хэл нь тогтмол биш үү, эсвэл үүнийг тодорхойлох арга замыг олох боломжгүй байсан уу гэдэг нь тодорхойгүй байна. Тухайн хэл нь тогтмол эсэхийг шалгах энгийн арга бий. Хэрэв тодорхой хэлний хувьд гэж нэрлэгддэг нь батлагдсан тэлэлтийн lemma, дараа нь энэ нь тогтмол байна. Хэрэв энэ лемма хангагдаагүй бол хэл нь тогтмол биш юм.

Өсөлтийн леммийг дараах байдлаар томъёолсон. Хэрэв энэ хэлэнд хамаарах ердийн хэл, хангалттай урт тэмдэгт гинж өгөгдсөн бол түүн дотроос хүссэнээрээ олон удаа давтаж болох хоосон бус дэд мөрийг олох боломжтой бөгөөд ийм аргаар олж авсан бүх хэлхээ нь мөн энэ хэлэнд хамаарах болно. ердийн хэл.

Албан ёсоор лемма нь дараах байдлаар бичигдсэн байдаг. Хэрэв L хэл өгөгдсөн бол p>0 тогтмол нь L ба p байвал гинжийг 0 хэлбэрээр бичиж болно.

Жишээ. L=(a n b n n>0) хэлийг авч үзье. Хэлний тархалтын тухай лемма ашиглан энэ нь тогтмол биш гэдгийг баталцгаая.

Энэ хэлийг тогтмол байг, тэгвэл өсөлтийн лемма нь үүнийг хадгалах ёстой. Энэ хэлний гинжийг = a n b n авч, хэлбэрээр бичье. Хэрэв a + эсвэл b + байвал i хэлхээ нь ямар ч i хэлний хувьд хамаарахгүй бөгөөд энэ нь леммын нөхцөлтэй зөрчилддөг. Хэрэв a + b + байвал 2-р хэлхээ нь мөн L хэлэнд хамаарахгүй. Бид зөрчилдөөнийг олж авсан тул хэл нь тогтмол биш юм.

Ердийн багцуудболон тогтмол илэрхийллүүд

Ердийн багцууд

Энэ хэсэгт бид хязгаарлагдмал толь бичигт хамаарах гинжин хэлхээний ангиллыг авч үзэх бөгөөд тэдгээрийг ямар нэг төрлийн томъёогоор тайлбарлахад хялбар байдаг. Эдгээр багцуудыг тогтмол гэж нэрлэдэг.

Тодорхойлолт 1.Болъё V 1 Тэгээд V 2 - олон гинж. Гурван үйлдлийг тодорхойлъёэдгээр багц дээр.

Холбоо: V 1 V 2 =(|   V 1 ) эсвэл   V 2 .

Холбогч (бүтээгдэхүүн, наалт): Vl V2 = (|  V 1 ,  V 2 ) Холбох үйлдлийн тэмдгийг ихэвчлэн орхигдуулдаг.

Жишээ: V, = (abc, ba),V 2 = (b, cb). V1V2 =(abcb, abccb, bab, bacb).

n олонлогийн үржвэрийг V n-ээр тэмдэглэе V:V n =VV...V,V° =() (энд  нь хоосон хэлхээ).

Жишээ: V 1 = (abc, ba), V 1 2 = (abcabc, abcba, baba, baabc).

3. Давталт: V* = V 0 V 1 V 2 ... =   =0 ∞ V n .

Жишээ: V = (a, bc), V* = (, a, bc, aa, abc, bcbc, bca, aaa, aabc,...).

Тодорхойлолт 4.13.Хязгаарлагдмал толь бичиг дээрх ердийн багцуудын ангиВ тодорхойлохдараах байдалтай байна:

нэгдэл ST;

ST холболт;

S* ба T* давталт.

5. Хэрэв 1-4-р дүрмийг эцэслэн ашигласнаар олонлог байгуулах боломжгүй бол энэ нь жигд бус байна.

Энгийн олонлогуудын жишээ: (ab, ba)* (aa); (b)((c)(d, ab)*). Тогтмол бус олонлогуудын жишээ: (a n b n | n > 0); ( | гинжин хэлхээнд  a ба b тэмдэгтүүдийн тохиолдлын тоо давхцдаг).

Тогтмол илэрхийлэл

Тогтмол олонлогууд нь сайн байдаг, учир нь тэдгээрийг бид ердийн илэрхийлэл гэж нэрлэх томъёогоор маш энгийнээр тайлбарлаж болно.

Тодорхойлолт 2.Хязгаарлагдмал толь бичиг дээрх ердийн илэрхийллийн ангиВ тодорхойлохдараах байдалтай байна:

тэдгээрийн нийлбэр R1+R2;

тэдний бүтээгдэхүүн R1R2;

тэдгээрийн давталт R1* ба R2*.

4. 1-3 дугаар дүрмийг хязгаартай хэрэглэж илэрхийлэл бүтээгдээгүй бол энэ нь тогтмол биш гэсэн үг.

Ажлын тэмдгийг орхигдуулж болно. Аливаа алгебрийн нэгэн адил хаалтны тоог багасгахын тулд үйл ажиллагааны тэргүүлэх чиглэлийг ашигладаг: давталт нь хамгийн чухал ач холбогдолтой; ажил нь ач холбогдол багатай; нэмэх нь хамгийн бага ач холбогдолтой.

Тогтмол хэллэгийн жишээ: ab + bа*; (aa)*b + (c + dab)*.

Тогтмол олонлогууд болон тогтмол хэллэгүүд маш ойрхон байгаа нь ойлгомжтой. Гэхдээ тэдгээр нь өөр өөр объектуудыг төлөөлдөг: ердийн багц нь гинжний багц (ерөнхий тохиолдолд хязгааргүй) юм тогтмол илэрхийлэл юмдээр дурдсан үйлдлүүдийг ашиглан харгалзах ердийн багцыг хэрхэн бүтээсэнийг бүдүүвчээр харуулсан томьёо(мөн энэ томъёо нь төгсгөлтэй).

R^ тогтмол илэрхийлэл R-д тохирох жирийн олонлог байг. Дараа нь:

Тиймээс тогтмол илэрхийлэл гэдэг нь хязгааргүй тооны хэлхээг, өөрөөр хэлбэл хэлийг тодорхойлсон төгсгөлтэй томьёо юм.

Тогтмол хэллэгүүд болон тэдгээрийн харгалзах хэлнүүдийн жишээг харцгаая.

Тогтмол илэрхийлэл	Харгалзах хэл
	b-ээс эхэлсэн бүх тэмдэгтүүд, дараа нь дурын тооны тэмдэгт a
	b-ийн яг хоёр тохиолдлыг агуулсан a ба b-ийн бүх мөрүүд
	b тэмдэгтүүд зөвхөн хосоор гарч ирдэг a ба b бүх хэлхээнүүд
(a+b)*(aa+bb)(a+b)*	Хамгийн багадаа нэг хос зэргэлдээ a эсвэл b агуулсан a ба b бүх гинж
(0+1)*11001(0+1)*	11001 дэд гинжийг агуулсан 0 ба 1-ийн бүх гинж
	a-аас эхэлж, b-ээр төгссөн бүх a ба b мөрүүд

Мэдээжийн хэрэг, мөрийн багц нь тогтмол илэрхийллээр төлөөлүүлж чадвал тогтмол байдаг. Гэсэн хэдий ч, ижил хэлхээг өөр өөр тогтмол хэллэгээр илэрхийлж болно, жишээлбэл, a тэмдэгтээс бүрдэх ба хамгийн багадаа хоёр a агуулсан хэлхээг дараах илэрхийллээр илэрхийлж болно: aa*a; а*аа*; ааа*; а*аа*аа* гэх мэт.

Тодорхойлолт 3.Хоёр тогтмол илэрхийлэл R1 Тэгээд R2 эквивалент гэж нэрлэдэг (тэмдэглэсэн Rl = R2) дараа нь, зөвхөн хэзээР1 ^ = Р2 ^ .

Тиймээс аа*а = а*аа* = ааа* = а*аа*аа*. Хоёр тогтмол илэрхийллийн тэнцлийг хэрхэн тодорхойлох вэ гэсэн асуулт гарч ирнэ.

Теорем1 . Аливаа тогтмол илэрхийллийн хувьдР, С ТэгээдТ шударга:

Эдгээр хамаарлыг харгалзах гинжин хэлхээний тэгш байдлыг шалгах замаар баталж болно. Тэдгээрийг ердийн хэллэгийг хялбарчлахад ашиглаж болно. Жишээ нь: b (b + aa*b) = b (b + aa*b) = b ( + aa*) b = ba*b. Эндээс b (b + aa*b) = ba*b, энэ нь тодорхойгүй байна.

Клиний теорем

Тогтмол хэллэгүүд нь ердийн хэлийг тодорхойлдог эцсийн томъёо юм. Гэхдээ хязгаарлагдмал төлөвт машинууд нь мөн ижил төстэй шинж чанартай байдаг - тэд бас хэлийг тодорхойлдог. Асуулт гарч ирнэ: хязгаарлагдмал төлөвт машинууд болон тогтмол хэллэгүүдээр тодорхойлсон хэлний ангиуд хоорондоо хэрхэн холбогддог вэ? гэж тэмдэглэе Мөн олон автомат хэл, R бол ердийн хэлний багц юм. Америкийн математикч Стивен Клин дараах теоремыг баталжээ.

Теорем2 . (Клиний теорем.) Ердийн олонлогууд болон автомат хэлүүдийн ангиуд давхцдаг, өөрөөр хэлбэл A = Р .

Өөрөөр хэлбэл, автомат хэл бүрийг томьёогоор (тогтмол илэрхийлэл) тодорхойлж, ердийн багц бүрийг хязгаарлагдмал автоматаар таних боломжтой. Бид энэ теоремыг хоёр үе шаттайгаар бодитоор батлах болно. Эхний алхамд бид аливаа автомат хэл нь ердийн олонлог гэдгийг нотлох болно (эсвэл ямар ч төгсгөлтэй автоматын хувьд бид энэ автоматаар хүлээн зөвшөөрөгдсөн хэлийг тодорхойлсон тогтмол илэрхийлэл үүсгэж болно). Хоёрдахь алхамд бид аливаа ердийн олонлог автомат хэл гэдгийг нотолж байна (эсвэл ямар ч тогтмол илэрхийллээс харгалзах ердийн олонлогийн гинжийг яг таг хүлээн зөвшөөрсөн төгсгөлтэй автоматыг байгуулж болно).

Хязгаарлагдмал автомат загварын ерөнхий дүгнэлт болгон шилжилтийн график загварыг танилцуулъя. Шилжилтийн график нь нэг эхний болон дурын тооны төгсгөлийн оройтой бөгөөд чиглүүлсэн ирмэгүүд нь хязгаарлагдмал автоматаас ялгаатай нь тэмдэгтээр биш, харин тогтмол илэрхийллээр тэмдэглэгдсэн байдаг. Шилжилтийн график нь a if гинжийг хүлээн зөвшөөрдөг Ань R 1 R 2 ...R n тогтмол илэрхийллийн үржвэрээр дүрслэгдсэн гинжин хэлхээний багцад хамаарах бөгөөд эхний оройноос эцсийн оройн аль нэг рүү хүрэх замыг тэмдэглэнэ. Шилжилтийн графикаар зөвшөөрөгдсөн хэлхээний багц нь түүний зөвшөөрөгдсөн хэлийг бүрдүүлдэг.

Цагаан будаа. 1. Шилжилтийн график

Зураг дээр. Эцсийн төлөв q руу хүргэдэг s->r->p->s->r->q зам нь гинжээр тэмдэглэгдсэн тул жишээ нь abbca гинжийг зөвшөөрдөг шилжилтийн графикийг Зураг 1-д үзүүлэв. тогтмол хэллэг ab* c*a. Хязгаарлагдмал төлөвийн машин нь шилжилтийн графикийн онцгой тохиолдол тул төрийн машинд хүлээн зөвшөөрөгдсөн бүх хэлийг шилжилтийн графикаар дэмждэг.

Теорем 3.Автомат хэл бүр нь ердийн багц, А  Р.

Баталгаа. Эхний болон төгсгөлийн нэг оройтой шилжилтийн график нь эхний цэгээс эцсийн орой хүртэлх цорын ганц ирмэгийг тогтмол R илэрхийллээр тэмдэглэсэн бөгөөд R ^ хэлийг хүлээн зөвшөөрдөг (Зураг 1).

Цагаан будаа. 2. Энгийн хэлний FT-г зөвшөөрсөн шилжилтийн график

Автомат хэл бүр нь ердийн олонлог гэдгийг одоо зөвшөөрөгдсөн хэлээ өөрчлөхгүйгээр аль ч шилжилтийн графикийг багасгаж, ижил хэлбэрт оруулан баталцгаая (Зураг 2).

Аливаа хязгаарлагдмал автомат болон шилжилтийн графикийг үргэлж нормчлогдсон хэлбэрээр дүрсэлж болох бөгөөд үүнд зөвхөн гарч буй ирмэгүүдтэй зөвхөн нэг анхны орой, зөвхөн ирж буй ирмэгүүдтэй зөвхөн нэг эцсийн орой байдаг (Зураг 3).

Цагаан будаа. 3. Нэг эхний болон нэг эцсийн оройтой шилжилтийн график

Шилжилтийн графикийг хэвийн хэлбэрт оруулснаар энэхүү шилжилтийн графикийн зөвшөөрөгдсөн хэлийг хадгалахын зэрэгцээ хоёр багасгах үйлдлийг гүйцэтгэх боломжтой - ирмэгийг багасгах ба оройг багасгах:

a) хавирга багасгах:

Б ) оройн бууралт (p оройгоор дамжин өнгөрөх зам бүрт орлуулалтыг хийж, дараа нь хүрэх боломжгүй төлөв байдлаар устгана):

Мэдээжийн хэрэг, багасгах үйлдэл бүр нь шилжилтийн графикаар хүлээн зөвшөөрөгдсөн хэлийг өөрчилдөггүй, харин ирмэгүүдийн тоо эсвэл оройн тоог багасгадаг бөгөөд эцэст нь бууралтууд нь шилжилтийн графикийг Зураг дээр үзүүлсэн хэлбэрт хүргэх болно. 2. Теорем нь батлагдсан: автомат хэл бүр ердийн олонлог юм.

Жишээ

Хязгаарлагдмал А машиныг өгье:

Бид эквивалент шилжилтийн графикийг хэвийн хэлбэрт оруулдаг.

Оройн бууралт 3:

Нумыг багасгах, R = R дүрмийг хэрэглэх:

Оройн бууралт 2:

1-р нум ба оройг багасгах:

Ийнхүү А автоматаар танигдсан хэлийг R A = b+(a+bb)(b+ab)*a тогтмол илэрхийллээр өгөгдсөн.

Клиний теоремыг нөгөө чиглэлд баталъя.

Теорем 2.Ердийн багц бүр автомат хэл юм: R А.

Баталгаа. R тогтмол илэрхийлэл бүрийн хувьд R-ийн заасан хэлийг таних хязгаарлагдмал автомат A r (магадгүй тодорхойгүй) бүтээгдэж болохыг харуулъя. Бид ийм автоматыг рекурсив байдлаар тодорхойлох болно.

(А-ийн эхний ба эцсийн төлөвүүд нийлсэн).

Жишээ(үргэлжлэл)