Előadás 3 kalkulus
Kalkulus. Formális rendszerek.
Formai nyelvtan. gépek
Van egy osztály a problémák, a matematikai modellek és algoritmusok, amelyek megoldása kényelmesen formájában mutatják be a formális kövek. Együtt a gép államok és funkciók kiszámítható algoritmus „algoritmus fogkő” egy harmadik fajta fogalmának tisztázását az algoritmus. program kialakítása technológia alapján hivatalos vesekő, vannak bizonyos jellemzői, és amelyet az ebben a fejezetben.
1. fogkő és formális rendszerek
Értelmes fogkő meghatározza konstruktív módon generálására szó egy nyelvet. Például Newton fogkő véges különbségek lehetővé teszi, hogy létrehoz (kiszámítani) a helyes kifejezést képletek differenciálművekhez minden egyenértékű kifejezés, mivel a szabályok identitás transzformációk. ítéletlogika lehetővé konstruktívan az összes lehetséges logikai törvények formájában azonosan igaz állításokat. Levezethető formális elmélet lehetővé teszi számunkra, hogy állítson össze egy olyan rendszer képletek, amelyek igazak a kiválasztott értelmezést.
1.1. Kiszámítása Thue (norvég matematikus Thue megfogalmazott a leggyakoribb modell számítási 1912)
ahol - egy véges ábécé
- a szabályok helyettesítések, ahol a (- szó az ábécé A). A * - minden szó az ábécé; szabályok „munka” mindkét irányban.
Ez lehetővé teszi, hogy konstruktív megoldására két fő feladata - a feladat létrehozása és feladata szófelismerési tagjai az IT.
a) A probléma a generációs egyenértékű szó benne.
Set szót az összes lehetséges szavak W. kimenet Z szabályai szerint a P IT. A több szó kimenete Z. úgynevezett ekvivalencia osztály Z. és az összes ilyen a, hogy a nevezett ekvivalens (W).
b) A probléma a egyenértékűségének elismeréséről szó pár.
ZW (ekvivalens) ha Z származtatható a szabályok szerint a szó W P.
Az, hogy a szabályok alkalmazása problémák megoldására nincs szabályozva, és megfelelően elvégzett egy fa teljes keresést.
1. példa, ahol - üres halmaz. Ez jelenti Markov Szó húr.
A „ABA” az IT származtatható többféleképpen (szabályai sorrendben).
1.2. Kiszámítása Herbrand - Gödel. (IUE)
1934-ben, Herbrand és nem függetlenül, mint Gödel fogalmának tisztázása algoritmus építésére formális kalkulus kiszámolni az összes lehetséges funkciót a természetes számok halmaza.
b) PPF - jól formált formulák, amelyek állnak kifejezések, épített szabályok szerint elfogadott matematika, és azzal a céllal, - és ahol - értelemben.
- wildcard számok helyett egy változó neve
- csere (szubsztitúció) az ábrán a kifejezés (szám).
Példa 2. Állítsa PPF rendszer.
Számolja funkció értékek
Ha meghatározzuk a rendszer PPF mint az összeadást
akkor a szabály szerint.
Az algoritmus a fogkő Herbrand - Gödel nem határozza meg a sorrendben szabályainak alkalmazásával helyettesítések és nem határozza meg, még permutációk rendszer, ahogy az szokás a Kleene rekurzív függvények. És minden fogalmának algoritmus (MT, USA, Oroszország) IUE formalizmus épül csak a transzformációk a szimbólumok sorozatát, és nem igényel semmilyen szemantika.
2. Ünnepélyes Rendszer (FS)
Formális rendszer számozva vannak, ahol az elkülönített részét olyan (szó), amely eredetileg meghirdetett kiadjuk. Ezek a képletek nevezzük axiómák.
a) PPF - jól formált képletek az ábécé,
b); A * - szókészletet épült az ábécé.
c) - egy axióma egy részhalmaza a PPF.
g) PV - típusú szabályokat, ami azt jelenti, a készlet származtatható PPF PPF. Mindenesetre készlet FS PPFV képletek származó PPFA szabályok használatával MF. Így PPFV> PPF> - úgynevezett levezethetők képletek.
Például, a ítéletlogika egy formális rendszer, amelyben PPF képletű gyártani változó nevét, jelek műveletek ( - összefüggésben, - diszjunkció, - negáció, - közvetve) és konzolok. Lekötött PPF, amely kimondta az egyetlen axiómák és következtetési szabály «Modus ponens». A ítéletlogika generált csak ilyen PPF. amely úgy értelmezhető, mint a valódi személyazonosságát az (tautológia), és csak ezek.
3. Formai nyelvtan (FG)
A fogkő formában javasolta az amerikai matematikus FS Chomsky (1953), az első, hogy megoldja a problémákat, a strukturális nyelvészet, és a további leírás formális nyelvek.
FG =. ahol A - a terminál ábécé
- kiegészítő ábécé, az S - az egyetlen axióma P - szabályok formájában, és ahol.
FG generál jellemző nyelv, mint egy része a szavak. FG szabályok nem tartalmaz korlátozást a rekurzív helyettesítések.
4. Automatikus és nyelvtani
a) A végső ábécé - terminális ábécé (kisbetűvel).
b) - az összes szó származik az ábécé betűi - üzemeltetés iteráció hozzárendelés (összefűzés). Például a szó = aabcc származó „a” a jóváírás a betűk „a” az „a” betű - továbbra is kap egy sorozata tulajdonították szó leveleket.
c) - a nyelv általános tartalmaz egy végtelen számú szó. Van egy probléma leírását nyelv használata a vége és a design tárgyak (például a képleteket, vagy szabályai generáció).
Mint mindig, úgy véljük, két fő célja van.
g) okozó yazykaL. A termelés a szó egy különleges design - generatív grammatika G. amely egy véges halmaza produkciók (szabályok helyettesítések) megjelenítéséhez bármely nyelv szavai különleges szimbólum S (axiómák), és csak azokat.
A - az alap ábécé, V - kisegítő ábécé - axióma
- Magyarország ábécé, R - szabályok (helyettesítő termékek) a formája, ahol (általában) (a szó a közös ábécé)
e) elismerése szavak yazykaL. Mivel a padló , vagy meghatározza. A probléma megoldására vannak elismerve gépek. Formálisan meghatározott automata - ahol A - az alap ábécé, S - állami ábécé P - típusú szabályokat, si. wi Sj. .
4.1. Automata (rendszeres) nyelvtan és -AG
állapotú gép - az űrhajó.
Automata nyelvtan, ahol A - az alap ábécé; P - szabályok formájában - egy axióma. Állami gép, ahol A - az alap ábécé; S - ábécé államok; s0 - kezdeti állapot; sk - a végső állapot; P - típusú szabályok
3. példa L1 nyelv beállítása:
egy halmaza az automata
A - A vég-jelölő szó
Ar történő átmenet szabályainak szabályok porozhdeniyaKA-
AG generál szavak a nyelv L1 L1 CA elismeri szavak a nyelv.
Ha megad szabályok AG, az FB a jogot, hogy megkapja a hivatalos jellegű Egy műszakban a jobb oldalon a szabályok balra (lásd. Példa). Ha meg van adva az FB szabályok, a szabályok a magas vérnyomás A kötőjel a jobb oldali részén a szabályokat.
SC adott átmenet grafikonon, és lényegében egy olyan gép (SM).
Ezenkívül automata nyelv által definiált reguláris kifejezés (képlet a betűk, jelek műveleteket: «» - konkatenációra «» - ismétlés „” közös „vagy”). A 3. példa, a reguláris kifejezést az L1 = ().
4. példa Legyen a nyelv L2 az ábrán adott a grafikont a szót, azt mondják, hogy felismeri a SC, ha a keresetet kap, hogy .Slovo nem ismeri CA; SC az intézkedés alapján S0 w2 maradnak S1. mert nincs szabály a kimenetre S1 hatása alatt bármilyen karaktert, kivéve a «b» és «».
A reguláris kifejezés a nyelv, a szavak által felismert az FB.
5. példa megkötése egy szót a AG 3. példa.
Szerzés a szó ki aaacbbb. A bekarikázott számok jelölt szabályokat.
4.2. Kleene tétel. (Előre és hátra)
a) egy reguláris kifejezés építhető űrhajó
b) Az űrhajó építhető egy reguláris kifejezés
Formálisan, minden állam gép egy véges állapotú gép, és így tovább SM kiterjed Kleene tétel.
5. A környezetfüggetlen nyelvtanok és bolti lopások
gépek. Környezetfüggetlen nyelvek.
Vannak nyelvek, amelyek nem írhatók le egy reguláris kifejezés, és ezért nem épül űrhajó, ami felismeri a szavakat a nyelvet.
Egy példa az ilyen nyelv, ahol számos ... b és L3 ugyanazt a szót, mint a szó és a szó.
A környezetfüggetlen nyelvtan (DRG).
A - nyelv ábécé (terminális ábécé) =; V- kisegítő ábécé =, ahol - a kezdeti szimbólumot - egy axióma ( „kezdet”); - társítja az ábécé R - szabályok a forma, ahol - a szót a betűk az ábécé egyesült.
6. példa generatív nyelvtan
Termelési szabályok (helyettesítő termékek)
1. Szerzés a szó ki aaacbbb
Ellentétben AH nyelvtan 3. példa, amely termel a beszéd és a köztük KCG példa 6 generál szavak azonos mennyiségű «a» és «b», és csak azokat.
Nyelvek, amelyek által COP - nyelvtanok nevezik kontextus-svobodnymiyazykami.
Kapcsolódó dokumentumok:
rendszeres készletek és kifejezések, véges automaták. Előadás 12 Nyelvtanok és felismerők O lánc. és R jelentése az egyes formalnoysisteme. például mennyiségben algebra, algebrai halmazok, a ítéletlogika és r. f. pl.
logikai programozási elv. Formai (axiomatikus) rendszer. A koncepció formalnoysistemy. hivatalos megkötésére. Ítéletlogika mint formalnayasistema. levonás tétel.
Nyelvészet, különösen az úgynevezett transzformációs nyelvtan. által kifejlesztett Chomsky. Semmi. formalnymisistemami. kapunk a fejlesztés eredményeként a természetes tudományok (például differenciál, integrálszámítás.
formális logika feltételes, és függ a megállapodást? És itt-ott. Bár calculi belül logika. Grammar nem működik a szót, és a szókincs. Között 1934-ben és! 93b éves B. az előadások. divitelno hogy a gépek és a fiziológiai rendszer fedezhető.
oktatás: gyakorlatok, nyelvtan. és a zene. Munkáját „Előadások az ipari. ítéletlogika elemi kijelentéseket. " Ez formalnoysisteme. levezethető a másik rendszerben. több. Létrehozása termelési gépek. teljesítő mag.