Хэл эсэх нь асуулт Тогтвортой эсэх нь тооцооллын нарийн төвөгтэй байдлын онол, ялангуяа албан ёсны хэл, автоматын онолыг судлах үндсэн сэдэв юм. Энэ ойлголтыг ойлгохын тулд ердийн хэлнүүдийн тодорхойлолт, шинж чанарууд болон тэдгээрийг хүлээн зөвшөөрдөг тооцооллын загваруудыг сайтар ойлгох шаардлагатай.
Тогтмол хэл ба хязгаарлагдмал автомат
Тогтмол хэлүүд нь хязгаарлагдмал тооны төлөвтэй хийсвэр машинууд болох хязгаарлагдмал автоматаар танигдах хэлний анги юм. Эдгээр хэлийг мөн ердийн хэллэг ашиглан дүрсэлж болох ба ердийн дүрмийн дагуу үүсгэж болно. Энгийн хэлнүүдийн гол шинж чанар нь тэдгээрийг детерминист төгсгөлтэй автомат (DFA) эсвэл тодорхойгүй төгсгөлтэй автоматаар (NFA) таних боломжтой байдаг. DFA нь төлөвүүдийн хязгаарлагдмал багц, оролтын тэмдэгтүүдийн багц, төлөв-тэмдгийн хосыг төлөвт буулгах шилжилтийн функц, анхны төлөв, хүлээн авах төлөвүүдийн багцаас бүрдэнэ.
Хязгаарлагдмал автоматуудын хүч нь тэдний хязгаарлагдмал санах ойгоор хязгаарлагддаг. Тэд тогтсон тооноос цааш тоолж чадахгүй бөгөөд энэ нь автомат машин дахь төлөвийн тоогоор хязгаарлагдахгүй бол тодорхой тэмдэгтийн дурын тооны тохиолдлыг хянах боломжгүй гэсэн үг юм. зэрэг хэлийг авч үзэхэд энэ хязгаарлалт нь чухал юм .
Тогтмол бус байдал
Хэл ердийнх эсэхийг тодорхойлохын тулд энгийн хэлнүүдийн хувьд Pumping Lemma-г ашиглаж болно. Pumping Lemma нь бүх ердийн хэлүүд хангагдсан байх ёстой шинж чанарыг өгдөг бөгөөд энэ шинж чанарыг хангахгүй байгаа нь тодорхой хэлүүд тогтмол биш гэдгийг харуулахад ихэвчлэн ашиглагддаг.
Pumping Lemma-д ямар ч энгийн хэлний хувьд гэж заасан байдаг , шахах урт байдаг
ямар ч мөр
in
урттай
гурван хэсэгт хувааж болно,
, дараах нөхцлийг хангасан:
1. ,
2. Болон
3. бүгдэд нь , мөр
байна
.
Үүнийг харуулахын тулд Pumping Lemma-г ашиглах тогтмол биш, зөрчилдөхийн тулд гэж бодъё
тогтмол байдаг. Дараа нь шахах урт байдаг
ямар ч мөр
in
хамтран
хэсэгт хувааж болно
шахах лемма-ийн нөхцлийг хангах.
Мөрийг анхаарч үзээрэй in
. Pumping Lemma-ийн дагуу,
хувааж болно
ийм байна
болон
. Учир нь
, дэд мөр
зөвхөн 0-ээс бүрдэнэ. Тиймээс,
,
Болон
хаана
.
Одоо мөрийг анхаарч үзээрэй . 0-ийн тоо
-ээс их байна
, харин 1-ийн тоо хэвээр байна
. Тиймээс,
Учир нь 0 ба 1-ийн тоо тэнцүү биш юм. Энэ зөрчил нь таамаглал байгааг харуулж байна
тогтмол бол худал. Тиймээс,
ердийн хэл биш.
Контекстгүй хэл ба түлхэх автомат
Хэл гэхдээ контекстгүй хэл (CFL). Контекстгүй хэлүүдийг түлхэх автоматаар (PDA) хүлээн зөвшөөрдөг бөгөөд тэдгээр нь хязгааргүй их хэмжээний мэдээллийг хадгалахын тулд стекийг ашиглаж чаддаг тул хязгаарлагдмал автоматуудаас илүү хүчтэй байдаг. Энэхүү нэмэлт санах ой нь PDA-д хэл дээрх 0 ба 1-ийн тоог хянах боломжийг олгодог
.
нь PDA дараах байдлаар ажилладаг.
1. Энэ нь эхний төлөвөөс эхэлж, оролтоос 0-г уншиж, 0 бүрийг стек рүү түлхэнэ.
2. Эхний 1-ийг уншсаны дараа энэ нь шинэ төлөвт шилжиж, оролтоос уншсан 0 тутамд стекээс 1-г гаргаж эхэлдэг.
3. Хэрэв оролт дууссан үед стек хоосон байвал PDA нь оролтыг хүлээн авч, 0-ийн тоо 1-ийн тоотой таарч байгааг илтгэнэ.
0 ба 1-ийн тоонд тохируулан стек ашиглах энэхүү механизм нь PDA-ууд ердийн биш боловч контекстгүй хэлийг таних чадварыг харуулж байна.
Жишээ ба цаашдын үр дагавар
Жишээ мөрийг авч үзье хэлнээс
. PDA нь энэ мөрийг уншиж байх үед 0 тус бүрийг стек рүү түлхэж боловсруулдаг. Гурван 0-г уншсаны дараа стек нь тус бүр нь 0-ийг төлөөлдөг гурван тэмдэгтийг агуулна. PDA дараагийн 1-үүдийг унших үед 1 тус бүрд стекээс нэг тэмдэг гарч ирнэ. Оролтыг бүрэн уншсан үед стек хоосон байна. оролтыг хүлээн зөвшөөрч байна.
Үүний эсрэгээр, хязгаарлагдмал автомат машин нь стек механизмгүй тул 0 ба 1-ийн тоог хянах боломжгүй болно. Хязгааргүй тооны тэмдэгтүүдийг хадгалах, сэргээх чадваргүй бол хязгаарлагдмал автомат машин нь 0-ийн тоог 1-ийн тоотой тэнцүү байлгах боломжгүй бөгөөд энэ нь хэлийг таних чадваргүй болоход хүргэдэг. .
Энгийн болон контекстгүй хэлийг ялгах нь онолын компьютерийн шинжлэх ухаанд чухал ач холбогдолтой бөгөөд програмчлалын хэлний дизайн, задлан шинжлэх зэрэг салбарт практик ач холбогдолтой. Контекстгүй хэлүүдийг үүсгэдэг контекстгүй дүрмүүд нь програмчлалын хэлний синтаксийг тодорхойлоход өргөн хэрэглэгддэг. PDA-г ашиглан контекстгүй хэлийг үр дүнтэй таних чадвар нь хөрвүүлэгч болон орчуулагчдын үндэс суурь болох задлан шинжлэгчийг хөгжүүлэх үндэс суурь болдог.
Тогтмол бус байдал Энэ нь хязгаарлагдмал автоматуудын хязгаарлалтыг онцолж, илүү өргөн хүрээний хэлийг танихын тулд түлхэх автомат гэх мэт илүү хүчирхэг тооцооллын загваруудын хэрэгцээг онцолж байна. Энэ ялгаа нь зөвхөн онолын хувьд биш, харин програмчлалын хэл, тэдгээрийг боловсруулах хэрэгслүүдийн практик дизайн, хэрэгжилтэд гүн гүнзгий нөлөө үзүүлдэг.
Сүүлийн үеийн бусад асуулт, хариулт EITC/IS/CCTF Тооцооллын нарийн төвөгтэй байдлын онолын үндэс:
- Палиндромыг уншиж чаддаг PDA-г авч үзвэл оролт нь нэгдүгээрт, палиндром, хоёрдугаарт палиндром биш байх үед стекийн хувьслыг нарийвчлан хэлж чадах уу?
- Детерминистик бус PDA-уудыг авч үзвэл мужуудын суперпозиция нь тодорхойлолтоор боломжтой юм. Гэсэн хэдий ч детерминистик бус PDA нь зөвхөн нэг стектэй байдаг бөгөөд энэ нь нэгэн зэрэг олон төлөвт байж болохгүй. Энэ яаж боломжтой вэ?
- Сүлжээний урсгалд дүн шинжилгээ хийх, аюулгүй байдлын болзошгүй зөрчлийг илтгэх хэв маягийг тодорхойлоход ашигладаг PDA-ийн жишээ юу вэ?
- Нэг хэл нөгөө хэлээсээ илүү хүчтэй гэдэг нь юу гэсэн үг вэ?
- Контекст мэдрэмтгий хэлүүдийг Тьюрингийн машин таних боломжтой юу?
- Тэгш тооны '1' тэмдэгт бүхий хоёртын мөрийг таних FSM-г хэрхэн тодорхойлж, 1011 оролтын мөрийг боловсруулахад юу болдгийг харуулах вэ?
- Нотертерминизм нь шилжилтийн функцэд хэрхэн нөлөөлдөг вэ?
- Энгийн хэлүүд нь хязгаарлагдмал төрийн машинуудтай тэнцэх үү?
- PSPACE анги нь EXPSPACE ангитай тэнцэхгүй байна уу?
- Алгоритмын хувьд тооцоолж болох асуудал нь Тьюрингийн машинаар тооцоолж болох асуудал мөн үү?