Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
1. Pomocou viacerých PDA: Najjednoduchší a najpriamejší prístup je vytvoriť samostatný PDA pre každý jazyk, ktorý chcete prijať. Je to podobné tomu, že má viac programov, z ktorých každý je venovaný konkrétnej úlohe. Ak sú uvedené so vstupným reťazcom, potrebujete mechanizmus (napr. Presportér alebo selektor), aby ste určili, ktorý PDA sa má použiť na základe nejakej charakteristiky vstupu.
2. Pomocou jedného PDA s upraveným vstupom: Mohli by ste potenciálne navrhnúť PDA, ktorý akceptuje * Úniu viacerých jazykov, ale to si vyžaduje starostlivé kódovanie vstupu. Do vstupného reťazca by ste mali pridať ďalšie informácie, aby ste označili, do ktorého jazyka patrí reťazec. Táto „ďalšia informácia“ by mohla byť predponou, príponou alebo vloženými markermi. Prechody PDA by boli potom navrhnuté tak, aby najprv identifikovali identifikátor jazyka a potom pokračovali v analýze na základe identifikovaného jazyka. Tento prístup sa môže stať komplexným v závislosti od počtu a povahy jazykov. Efektívne simuluje viac PDA v rámci jedného automatu.
3. Použitie stavu stroja ako preprocesor: Vytvorte deterministický konečný automatický automobil (DFA), ktorý bude pôsobiť ako preprocesor. Tento DFA by analyzoval vstup a určil, ktorý jazyk, do ktorého reťazec pravdepodobne patrí. Na základe výstupu DFA by sa príslušná PDA vybrala zo súboru PDA. Tento prístup oddeľuje identifikáciu jazyka od analýzy, vďaka čomu je dizajn potenciálne čistejší a modulárnejší ako predchádzajúca metóda.
Príklad (Metóda 2 - Single PDA s modifikovaným vstupom):
Povedzme, že chceme prijať dva jazyky:
* L1: Jazyk palindrómov nad {a, b} (napr. „AA“, „ABA“, „Babbab“)
* L2: Jazyk reťazcov s rovnakým počtom „A a 'B (napr.„ AB “,„ Aabb “,„ Abab “)
Mohli by sme upraviť vstup tak, aby obsahoval značku:
* Pre L1:Predponu reťazec pomocou „1“. (napr. „1aba“)
* Pre L2:Predponu reťazec pomocou „2“. (napr. „2abab“)
PDA by potom:
1. Prečítajte si prvý symbol (1 alebo 2): To určuje, ktorý jazyk sa spracováva.
2. na základe prvého symbolu: Prechod do stavu zodpovedajúcej buď logike kontroly palindrómu (pre „1“) alebo logiku kontroly rovnakej A-a-B (pre „2“).
3. Spracujte zostávajúci reťazec: PDA používa svoj zásobník a prechody na prijatie alebo odmietnutie reťazca na základe pravidiel vybraného jazyka.
Dôležité úvahy:
* zložitosť: Metódy 2 a 3 sa môžu rýchlo stať neuveriteľne zložitými, ak máte veľa jazykov alebo ak sú jazyky veľmi zložité. Štátny diagram a tabuľka prechodu sa výrazne zvýšia.
* Účinnosť: Viacnásobné PDA (metóda 1) sú vo všeobecnosti efektívnejšie ako pokus o ich kombináciu, najmä pre veľké množstvo jazykov.
* nejednoznačnosť: V metóde 2 musí byť vstupné kódovanie jednoznačné. PDA musí byť schopná jasne určiť, ktorý jazyk sa spracováva na základe predpony alebo markera.
Stručne povedané, aj keď nemôžete priamo urobiť jeden PDA akceptovať viacero ľubovoľných jazykov súčasne, pomocou viacerých PDA alebo sofistikovaného prístupu s predbežným spracovaním je praktický spôsob, ako vyriešiť túto požiadavku. Výber závisí od zložitosti jazykov a obmedzení vášho dizajnu.