Taybetmendiya girtina zimanên birêkûpêk ên di bin hevgirtinê de çi ye? Makîneyên dewleta dawîn çawa li hev tên ku yekbûna zimanan bi du makîneyan tê naskirin temsîl bikin?

/ / Weşandin Pîroz, EITC/IS/CCTF Bingehên Teoriya Tevliheviya Hesabkirinê, Makîneyên Dewleta Dawî, Operasyonên li ser Zimanên Rêkûpêk

Taybetmendiyên girtina zimanên birêkûpêk û rêbazên ji bo berhevkirina makîneyên dewleta dawî (FSM) ji bo temsîlkirina operasyonên wekî yekbûn û hevgirtinê di teoriya hesabkirinê de têgehên bingehîn in û di warê ewlehiya sîber de, nemaze di analîzkirin û sêwiranê de, xwedî bandorên girîng in. algorîtmayên ji bo lihevhatina nimûneyê, pergalên tespîtkirina destavêtinê, û sepanên din.

Taybetmendiya Girtinê ya Zimanên Birêkûpêk di bin Tevhevkirinê de

Komeke zimanan tê gotin ku di bin operasyonekê de girtî ne, ger bi sepandina wê operasyonê li ser zimanên di nav rêzê de bibe sedema zimanek ku ew jî di nav rêzê de ye. Zimanên bi rêkûpêk, ku dikarin ji hêla makîneyên dewleta dawî ve bêne nas kirin, di bin çend operasyonan de têne girtin, di nav de yekbûn, hevberdan, temamkirin, û hevgirtin.

Ji bo operasyona hevgirtinê, heke L_1 û L_2 zimanên bi rêkûpêk in, paşê hevgirtin in L_1L_2 jî zimanekî rêkûpêk e. Têkiliya du zimanan L_1 û L_2 wekî:

    \[ L_1L_2 = \{ xy \mid x \li L_1 \text{ û } y \li L_2 \} \]

Ji bo ku taybetmendiya girtinê di bin hevgirtinê de nîşan bidin, wê bifikirin L_1 û L_2 ji hêla makîneyên dewleta dawî ve têne nas kirin M_1 û M_2, bi rêzê ve. Armanc avakirina makîneyeke nû ya dewleta dawî ye M ku ziman nas dike L_1L_2.

Avakirina Makîneya Dewleta Dawî ya Ji bo Tevhevkirinê

Berdan M_1 = (Q_1, \Sigma, \delta_1, q_1, F_1) û M_2 = (Q_2, \Sigma, \delta_2, q_2, F_2) makînên dewleta dawîn be ku nas dikin L_1 û L_2, bi rêzê ve. Vir, Q_1 û Q_2 komên dewletan in, \Sigma alfabeya têketina hevpar e, \delta_1 û \delta_2 fonksiyonên veguherînê ne, q_1 û q_2 dewletên destpêkê ne, û F_1 û F_2 komên dewletên qebûlker in.

Ji bo avakirina makîneya dewleta dawî M ku nas dike L_1L_2:

1. Amerîka: Koma dewletan bo M is Q = Q_1 \ kûp Q_2. Ev tê vê wateyê M dê hemû dewlet ji herduyan hebin M_1 û M_2.

2. Elfabe: Alfabeya têketinê \Sigma wek xwe dimîne.

3. Fonksiyona Veguheztinê: Fonksiyona derbasbûnê \delta of M wiha tê pênasekirin:
- Ji bo dewletên di Q_1 û input a \li \Sigma, \delta wekî tevdigere \delta_1. Ku heye, \delta(q, a) = \delta_1(q, a) bo q \li Q_1.
- Ji bo dewletên di Q_2 û input a \li \Sigma, \delta wekî tevdigere \delta_2. Ku heye, \delta(q, a) = \delta_2(q, a) bo q \li Q_2.
- Bi ser de, ji bo her dewletek qebûlker f \ di F_1 de û têla vala \epsilon, \delta(f, \epsilon) = q_2. Ev veguhertin bi bingehîn dihêle ku makîne ji rewşek pejirandinê derkeve M_1 heya rewşa destpêkê ya M_2 bêyî ku tu têketinê bixwin.

4. Dewleta Destpêkê: Rewşa destpêkê ya M rewşa destpêkê ya M_1kî ye q_1.

5. Dewletên qebûl dikin: Koma dewletên qebûlkirî yên M is F = F_2. Ev wateya ku M stringek dipejirîne heke bigihîje rewşek pejirandinê M_2 piştî pêvajoya tevahiya string.

Bi şopandina vê avakirinê, M dê hevbendiya nas bike L_1 û L_2.

Mînak

Li du zimanên asayî binêrin L_1 = \{ a, ab \} û L_2 = \{ b, ba \}. Berdan M_1 û M_2 bibin makîneyên dewleta dawî naskirî L_1 û L_2, rêzdarî.

- M_1 dibe xwedî dewlet \{ q_1, q_2, q_3 \} bi veguherînan:
- \delta_1(q_1, a) = q_2
- \delta_1(q_2, b) = q_3
- F_1 = \{ q_2, q_3 \}

- M_2 dibe xwedî dewlet \{ p_1, p_2, p_3 \} bi veguherînan:
- \delta_2(p_1, b) = p_2
- \delta_2(p_2, a) = p_3
- F_2 = \{ p_2, p_3 \}

Avakirin M bo L_1L_2:

- Dewletên: \{ q_1, q_2, q_3, p_1, p_2, p_3 \}
- Veguhertinên di nav wan de hene M_1 û M_2, plus \delta(q_2, \epsilon) = p_1 û \delta(q_3, \epsilon) = p_1
- Rewşa destpêkê: q_1
- Dewletên qebûl: \{ p_2, p_3 \}

Tevhevkirina Makîneyên Dewleta Dawî yên ji bo Yekîtiyê

Yekbûna du zimanan L_1 û L_2 wekî:

    \[ L_1 \cup L_2 = \{ x \navenda x \li L_1 \navnîşan{ an } x \li L_2 \} \]

Ji bo avakirina makîneyeke dewleta dawî M ku yekbûna nas dike L_1 û L_2, em avakirina otomatê ya dawî ya ne-determînîst (NFA) bikar tînin. Ger M_1 = (Q_1, \Sigma, \delta_1, q_1, F_1) û M_2 = (Q_2, \Sigma, \delta_2, q_2, F_2) makîneyên dewleta dawî ji bo in L_1 û L_2, bi rêzê ve, avakirina M wiha ye:

1. Amerîka: Koma dewletan bo M is Q = Q_1 \kup Q_2 \{q_0 \}, ku q_0 dewleteke nû ya destpêkê ye.

2. Elfabe: Alfabeya têketinê \Sigma wek xwe dimîne.

3. Fonksiyona Veguheztinê: Fonksiyona derbasbûnê \delta wekî:
- \delta(q, a) = \delta_1(q, a) bo q \li Q_1
- \delta(q, a) = \delta_2(q, a) bo q \li Q_2
- \delta(q_0, \epsilon) = \{ q_1, q_2 \}. Vê veguheztinê dihêle ku makîneyê ne-determînîst hilbijêre ku dest pê bike M_1 or M_2.

4. Dewleta Destpêkê: Rewşa destpêkê ya M dewleta nû ye q_0.

5. Dewletên qebûl dikin: Koma dewletên qebûlkirî yên M is F = F_1 \ cup F_2.

Ev avahî wê piştrast dike M xêzekê dipejirîne eger ew ji hêla her yekê ve were pejirandin M_1 or M_2.

Mînak

Li du zimanên asayî binêrin L_1 = \{ a, ab \} û L_2 = \{ b, ba \}. Berdan M_1 û M_2 bibin makîneyên dewleta dawî naskirî L_1 û L_2, rêzdarî.

- M_1 dibe xwedî dewlet \{ q_1, q_2, q_3 \} bi veguherînan:
- \delta_1(q_1, a) = q_2
- \delta_1(q_2, b) = q_3
- F_1 = \{ q_2, q_3 \}

- M_2 dibe xwedî dewlet \{ p_1, p_2, p_3 \} bi veguherînan:
- \delta_2(p_1, b) = p_2
- \delta_2(p_2, a) = p_3
- F_2 = \{ p_2, p_3 \}

Avakirin M bo L_1 \ cup L_2:

- Dewletên: \{ q_0, q_1, q_2, q_3, p_1, p_2, p_3 \}
- Veguhertinên di nav wan de hene M_1 û M_2, plus \delta(q_0, \epsilon) = \{ q_1, p_1 \}
- Rewşa destpêkê: q_0
- Dewletên qebûl: \{ q_2, q_3, p_2, p_3 \}

Ev avahî nîşan dide ka makîneyên dewleta dawî çawa dikarin werin berhev kirin da ku yekîtiya zimanên ku ew nas dikin temsîl bikin, taybetmendiyên girtina zimanên birêkûpêk ên di bin yekbûn û hevgirtinê de destnîşan dike.

Pirs û bersivên din ên vê dawiyê di derbarê EITC/IS/CCTF Bingehên Teoriya Tevliheviya Hesabkirinê:

Pirs û bersivan bêtir li Bingehên Teoriya Tevliheviya Hesabkirinê ya EITC/IS/CCTF bibînin

Pirs û bersivên bêtir:

Tagged under: , , , , ,