Deterministik surish avtomati - Deterministic pushdown automaton - Wikipedia

Yilda avtomatlar nazariyasi, a deterministik surish avtomati (DPDA yoki DPA) ning o'zgarishi pastga tushirish avtomati. Deterministik pastga tushirish avtomatlari sinfi qabul qiladi kontekstsiz deterministik tillar, tegishli qism kontekstsiz tillar.^[1]

Mashina o'tishlari joriy holat va kirish belgisiga, shuningdek, stekning hozirgi eng yuqori belgisiga asoslanadi. Stekka pastroq bo'lgan belgilar ko'rinmaydi va darhol ta'sir qilmaydi. Mashina harakatlariga stak ustini itarish, ochish yoki almashtirish kiradi. Deterministik pastga tushirish avtomati kirish belgisi, holat va yuqori stek belgilarining bir xil kombinatsiyasi uchun ko'pi bilan bitta qonuniy o'tishga ega. Bu erda u nondeterministic pushdown avtomatidan farq qiladi.

Rasmiy ta'rif

A (aniqlovchi emas) PDA ${ displaystyle M}$ 7 karra sifatida belgilanishi mumkin:

{ displaystyle M = (Q ,, Sigma ,, Gamma ,, q_ {0} ,, Z_ {0} ,, A ,, delta ,)}

qayerda

${ displaystyle Q ,}$ holatlarning cheklangan to'plamidir
${ displaystyle Sigma ,}$ - bu kirish belgilarining cheklangan to'plami
${ displaystyle Gamma ,}$ sonli sonli to'plam belgilaridir
${ displaystyle q_ {0} , in Q ,}$ boshlang'ich holati
${ displaystyle Z_ {0} , in Gamma ,}$ boshlang'ich stek belgisi
${ displaystyle A , subseteq Q ,}$ , qayerda ${ displaystyle A}$ qabul qiluvchi holatlar to'plamidir
${ displaystyle delta ,}$ o'tish funktsiyasi, bu erda

{ displaystyle delta colon (Q , times ( Sigma , cup left { varepsilon , right }) ​​ times Gamma ,) longrightarrow { mathcal {P}} ( Q times Gamma ^ {*})}

qayerda

{ displaystyle *}

bo'ladi Kleene yulduzi, demak

{ displaystyle Gamma ^ {*}}

bu "barcha sonli satrlar to'plami (shu jumladan bo'sh satr

{ displaystyle varepsilon}

) ning elementlari

{ displaystyle Gamma}

",

{ displaystyle varepsilon}

belgisini bildiradi bo'sh satr va

{ displaystyle { mathcal {P}} (X)}

bo'ladi quvvat o'rnatilgan to'plamning

{ displaystyle X}

.

M bu deterministik agar u ikkala quyidagi shartlarni qondirsa:

Har qanday kishi uchun ${ displaystyle q in Q, a in Sigma cup left { varepsilon right }, x in Gamma}$ , to'plam ${ displaystyle delta (q, a, x) ,}$ ko'pi bilan bitta elementga ega.
Har qanday kishi uchun ${ displaystyle q Q, x in Gamma}$ , agar ${ displaystyle delta (q, varepsilon, x) not = emptyset ,}$ , keyin ${ displaystyle delta left (q, a, x right) = emptyset}$ har bir kishi uchun ${ displaystyle a in Sigma.}$

Ikkita qabul qilish mezonlari mavjud: tomonidan qabul qilish bo'sh stack va qabul qilish yakuniy holat. Ikkisi deterministik pushdown avtomati uchun teng emas (garchi ular deterministik bo'lmagan pushdown avtomatiga tegishli bo'lsa). Qabul qilingan tillar bo'sh stack tomonidan qabul qilingan tillar yakuniy holat va prefikssiz: tilda hech qanday so'z tildagi boshqa so'zning prefiksi emas.^{[iqtibos kerak ]}

Odatiy qabul qilish mezonlari yakuniy holatva aniqlanish uchun ushbu qabul qilish mezonidan foydalaniladi kontekstsiz deterministik tillar.

Tillar tanildi

Agar ${ displaystyle L (A)}$ PDA tomonidan qabul qilingan tildir ${ displaystyle A}$ , agar u DPDA tomonidan qabul qilinishi mumkin, agar faqat boshlang'ich konfiguratsiyadan tortib to barcha qatorlar uchun qabul qilinadigangacha bitta hisoblash bo'lsa. ${ displaystyle L (A)}$ . Agar ${ displaystyle L (A)}$ PDA tomonidan qabul qilinishi mumkin, bu kontekstsiz til va agar DPDA tomonidan qabul qilinishi mumkin bo'lsa, bu aniqlanadigan kontekstsiz til (DCFL).

Hamma kontekstsiz tillar ham deterministik emas. Bu DPDA-ni PDA-dan qat'iyan zaifroq qurilmaga aylantiradi. Masalan, til L_p juft uzunlikdagi palindromlar 0 va 1 alfavitida kontekstsiz S → 0S0 | grammatikasi mavjud 1S1 | ε. Agar ushbu til uchun DPDA mavjud bo'lsa va u 0 qatorini ko'rsaⁿ, uzunlikni eslab qolish uchun u o'z to'plamidan foydalanishi kerak n, uning mumkin bo'lgan davomini ajrata olish uchun 0ⁿ 11 0ⁿ ∈ L_p va 0ⁿ 11 0ⁿ⁺² ∉ L_p. Demak, o'qigandan keyin 0ⁿ 11 0ⁿ, "11" dan keyingi uzunlikni "11" gacha bo'lgan uzunlik bilan taqqoslasak, stack yana bo'sh bo'ladi. Shu sababli, torlar 0ⁿ 11 0ⁿ 0ⁿ 11 0ⁿ ∈ L_p va 0ⁿ 11 0ⁿ 0ⁿ⁺² 11 0ⁿ⁺² ∉ L_p ajratib bo'lmaydi.^[2]

DPDA-ni bitta holatga cheklash, qabul qilingan tillar sinfini kamaytiradi LL (1) tillari,^[3] bu DCFL-ning tegishli subklassi.^[4] PDA holatida ushbu cheklov qabul qilingan tillar sinfiga ta'sir qilmaydi.

Xususiyatlari

Yopish

Deterministik kontekstsiz tillarning yopilish xususiyatlari (yakuniy holat bo'yicha deterministik PDA tomonidan qabul qilinadi) kontekstsiz tillardan keskin farq qiladi. Misol tariqasida ular (samarali) komplementatsiya ostida yopiladi, lekin birlashma ostida yopilmaydi. Deterministik PDA tomonidan qabul qilingan tilning komplementi ham deterministik PDA tomonidan qabul qilinishini isbotlash juda hiyla-nayrangdir.^{[iqtibos kerak ]} Aslida cheksiz hisoblashlardan qochish kerak.

Komplementatsiya natijasida, aniqlovchi PDA barcha so'zlarni kirish alifbosi orqali qabul qiladimi, to'ldiruvchini bo'shligini tekshirib ko'rdi. Bu kontekstsiz grammatikalar uchun mumkin emas (shuning uchun umumiy PDA uchun emas).

Ekvivalentlik muammosi

Jerad Senizergues (1997) deterministik PDA (ya'ni ikkita deterministik PDA A va B berilgan, L (A) = L (B)?) Uchun ekvivalentlik muammosi hal qilinishini isbotladi,^[5]^[6]^[7] unga 2002 yilda erishgan dalil Gödel mukofoti. Nodeterministik PDA uchun ekvivalentlikni hal qilish mumkin emas.

Izohlar

^ Maykl Sipser (1997). Hisoblash nazariyasiga kirish. PWS nashriyoti. p.102. ISBN 0-534-94728-X.
^ Xopkroft, Jon; Rajeev Motvani; Jeffri Ullman (2001). Avtomatika nazariyasi, tillar va hisoblash bilan tanishish (2 nashr). Addison-Uesli. pp.249 –253.
^ Kurki-Suonio, R. (1969). "Yuqoridan pastga yo'naltirilgan tillarga eslatmalar". BIT. 9 (3): 225–238. doi:10.1007 / BF01946814.
^ Rozenkrantz, D. J .; Stearns, R. E. (1970). "Deterministik tepadan pastga grammatikasining xususiyatlari". Axborot va boshqarish. 17 (3): 226–256. doi:10.1016 / s0019-9958 (70) 90446-8. Bu erda: s.246-247
^ Senizergues, Jero (1997). "Deterministik pastga tushirish avtomatlari uchun ekvivalentlik muammosi hal qilinadi". Proc. Int. Coll. avtomatika, tillar va dasturlash bo'yicha (ICALP). Kompyuter fanidan ma'ruza matnlari. 1256. 671-681 betlar. doi:10.1007/3-540-63165-8_221. ISBN 978-3-540-63165-1. - To'liq versiya: Jerad Sénizergues (1997). L(A) = L(B)? (Texnik hisobot 1161-97). Universit Bordo, LaBRI.
^ Jerad Sénizergues (2001). "Fundamental o'rganish: L(A) = L(B)? qarorlilik to'liq rasmiy tizimlardan kelib chiqadi ". Nazariy kompyuter fanlari. 251 (1–2): 1–166. doi:10.1016 / S0304-3975 (00) 00285-1.
^ Jerad Sénizergues (2002). "L(A) = L(B)? Soddalashtirilgan qaror qabul qilishning isboti ". Nazariy kompyuter fanlari. 281 (1–2): 555–608. doi:10.1016 / S0304-3975 (02) 00027-0.

Qo'shimcha o'qish

Gamburger, Genri; Dana Richards (2002). Kompyuter fanlari uchun mantiq va til modellari. Yuqori Saddle River, NJ 07458: Prentice Hall. pp.284 –331. ISBN 0-13-065487-6.CS1 tarmog'i: joylashuvi (havola)

[1] Maykl Sipser (1997). Hisoblash nazariyasiga kirish. PWS nashriyoti. p.102. ISBN 0-534-94728-X.

[2] Xopkroft, Jon; Rajeev Motvani; Jeffri Ullman (2001). Avtomatika nazariyasi, tillar va hisoblash bilan tanishish (2 nashr). Addison-Uesli. pp.249 –253.

[3] Kurki-Suonio, R. (1969). "Yuqoridan pastga yo'naltirilgan tillarga eslatmalar". BIT. 9 (3): 225–238. doi:10.1007 / BF01946814.

[4] Rozenkrantz, D. J .; Stearns, R. E. (1970). "Deterministik tepadan pastga grammatikasining xususiyatlari". Axborot va boshqarish. 17 (3): 226–256. doi:10.1016 / s0019-9958 (70) 90446-8. Bu erda: s.246-247

[5] Senizergues, Jero (1997). "Deterministik pastga tushirish avtomatlari uchun ekvivalentlik muammosi hal qilinadi". Proc. Int. Coll. avtomatika, tillar va dasturlash bo'yicha (ICALP). Kompyuter fanidan ma'ruza matnlari. 1256. 671-681 betlar. doi:10.1007/3-540-63165-8_221. ISBN 978-3-540-63165-1. - To'liq versiya: Jerad Sénizergues (1997). L(A) = L(B)? (Texnik hisobot 1161-97). Universit Bordo, LaBRI.

[6] Jerad Sénizergues (2001). "Fundamental o'rganish: L(A) = L(B)? qarorlilik to'liq rasmiy tizimlardan kelib chiqadi ". Nazariy kompyuter fanlari. 251 (1–2): 1–166. doi:10.1016 / S0304-3975 (00) 00285-1.

[7] Jerad Sénizergues (2002). "L(A) = L(B)? Soddalashtirilgan qaror qabul qilishning isboti ". Nazariy kompyuter fanlari. 281 (1–2): 555–608. doi:10.1016 / S0304-3975 (02) 00027-0.

[1]

[2]

[3]

[4]

[5]

[6]

[7]