Limbaj formal

Un limbaj formal este un limbaj abstract în care, spre deosebire de limbile naturale, adesea nu comunicarea este în prim plan, ci utilizarea matematică. Un limbaj formal constă dintr-un anumit număr de șiruri de simboluri (în general șiruri de caractere ) („cuvinte” ale limbii), care pot fi puse împreună dintr-un set de caractere / simboluri („alfabet”, simboluri de bază). Limbajele formale sunt utilizate în lingvistică , logică și informatică teoretică .

Limbajele formale sunt potrivite pentru descrierea (matematică) precisă a manipulării șirurilor de caractere. De exemplu, pot fi specificate formate de date sau limbaje de programare întregi. Împreună cu semantica formală , șirurilor de caractere definite li se dă un sens (matematic). Într-un limbaj de programare, unei instrucțiuni de programare (ca parte a limbajului formal) i se poate atribui un comportament unic al mașinii (ca parte a semanticii ).

Pe baza limbajelor formale, totuși, se pot defini și calculele logice cu ajutorul cărora se pot trage concluzii matematice. În legătură cu limbaje de programare definite formal, calculii pot ajuta la verificarea corectitudinii programelor .

definiție

O limbă oficială de peste un alfabet este un subset de coajă trifoi cenușă a alfabetului: . ${\ displaystyle L}$${\ displaystyle \ Sigma}$${\ displaystyle L \ subseteq \ Sigma ^ {*}}$

Un alfabet definește caracterele din care se poate forma un „ cuvânt ” al limbii. De exemplu, puteți crea reprezentarea zecimală a oricărui număr natural din alfabet . ${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma = \ {0,1,2,3,4,5,6,7,8,9 \}}$

Toate cuvintele cu o lungime finită (lungimea 0 sau mai mare) care pot fi formate în mod arbitrar dintr-un alfabet dat și a cărui literă individuală este un element al acestei cantități cât mai mari de cuvinte pentru alfabet , se numește coaja Kleen a alfabetului , pe scurt . Un limbaj formal peste un alfabet este, prin urmare, un anumit subset al cochiliei Kleene a alfabetului dvs. - în general, nu orice combinație arbitrară de caractere este un cuvânt valid în limbă. ${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma ^ {*}}$${\ displaystyle \ Sigma}$

Limbajele formale pot fi goale, finite sau infinite; cel mult pot cuprinde întreaga coajă Kleenesche a alfabetului lor. Ele pot fi definite printr-o condiție matematică pe cuvintele lor: „Limbajul ... este ansamblul tuturor cuvintelor pentru care se aplică ...”.

Cu toate acestea, limbile utilizate în informatica teoretică sunt definite mai specific printr-o anumită procedură de înlocuire - reguli privind modul în care caracterele alfabetului sunt / pot fi combinate. Există diferite tipuri de metode de înlocuire: sisteme Semi-Thue , gramatici Chomsky , sisteme Lindenmayer și altele. Astfel de procese de înlocuire se bazează pe, de exemplu, un șir specific de caractere de început, care este transformat treptat în structuri de cuvinte prin aplicarea repetată („recursivă”) a regulilor (înlocuiri de text), care apoi în ansamblu sau doar o secțiune specificată din acestea, deoarece cuvintele se aplică limbii. Se vorbește și despre gramaticile generative aici , deoarece cuvintele unei limbi sunt generate pas cu pas prin astfel de substituții de text . În schimb, limbile pot fi definite și ca ansamblul tuturor cuvintelor din care poate fi generat un anumit cuvânt predefinit sau unul dintre mai multe cuvinte predefinite (prin procesul de înlocuire a limbajului). („Totul aparține limbajului care poate fi urmărit până la ... prin reguli.”)

Diferențierea de limbile naturale

Cu ajutorul limbajelor formale, pot fi modelate și limbile naturale , în special sintaxa lor. Cu toate acestea, atunci când se compară limbile formale cu limbile naturale, trebuie remarcat faptul că limbile naturale au cel puțin cele două niveluri ierarhice suprapuse ale cuvântului și propoziția de deasupra semnelor fonetice elementare . Regulile pentru structura lor sunt de obicei împărțite în morfologie pe de o parte și sintaxă pe de altă parte. În limbile formale, pe de altă parte, există adesea un singur nivel al ierarhiei cuvântului formal deasupra semnului alfabetului elementar ; în ceea ce privește structura cuvintelor, se vorbește despre sintaxă. Dacă un limbaj natural este modelat folosind unul formal, atunci propozițiile limbajului natural sunt numite cuvinte din punct de vedere formal .

În plus, enunțurile în limbajul natural au un sens natural, în timp ce sensul limbajelor formale trebuie întotdeauna definit într-un mod formal.

Exemple

1. Limbajul de programare C este un limbaj formal. Cuvintele din C sunt programele respective. Alfabetul lui C sunt cuvintele cheie și caracterele stabilite în definiția lui C.
2. Numerele naturale în reprezentare unară: ${\ displaystyle \ mathbb {N} _ {\ rm {un}}: = \ {\ varepsilon, 1,11,111,1111, \ ldots \}}$
3. Limbajul unar de mai sus , care conține doar cuvinte de lungime pătrată:${\ displaystyle \ {a \}}$${\ displaystyle {\ rm {quad \ _count}}: = \ {a ^ {(n ^ {2})} \ mid n \ in \ mathbb {N} \}}$
4. ${\ displaystyle {\ rm {count}} _ {2}: = \ {a ^ {n} b ^ {n} \ mid n \ in \ mathbb {N} \}}$
5. ${\ displaystyle {\ rm {count}} _ {3}: = \ {a ^ {n} b ^ {n} c ^ {n} \ mid n \ in \ mathbb {N} \}}$
6. Limbajul tuturor palindroame : , în cazul în care reflectarea a cuvântului este.${\ displaystyle {\ rm {pal}}: = \ {w \ in \ {0.1 \} ^ {*} \ mid w = w ^ {R} \}}$
   ${\ displaystyle w ^ {R}}$${\ displaystyle w}$
7. Zecimal de codificare a numerelor prime: . Aici codarea numerelor naturale denotă în sistemul zecimal și PRIM reprezintă ansamblul numerelor prime .${\ displaystyle {\ rm {prim}} _ {\ rm {dec}}: = \ {{\ rm {dec}} (p) \ mid p \ in {\ rm {PRIM}} \}}$
   ${\ displaystyle {\ rm {dec}} \ colon \ mathbb {N} \ rightarrow \ {0,1,2,3,4,5,6,7,8,9 \} ^ {*}}$
8. Morse sau Thue secvență : , în care un morfism este definit după cum urmează: și , . Astfel, primele elemente ale secvenței Thue sunt: ​​0, 01, 0110, 01101001, 0110100110010110 ...${\ displaystyle {\ rm {thue}}: = \ {h_ {t} ^ {n} (0) \ mid n \ in \ mathbb {N} \}}$
   ${\ displaystyle h_ {t}}$${\ displaystyle h_ {t} (\ varepsilon) = \ varepsilon}$${\ displaystyle h_ {t} (w0): = h_ {t} (w) 01}$${\ displaystyle h_ {t} (w1): = h_ {t} (w) 10}$
   

Operațiuni asupra limbajelor formale

Două limbi deasupra alfabetului și deasupra alfabetului sunt banale, ambele limbi sunt deasupra , adică seturi de cuvinte . Prin urmare sunt și ${\ displaystyle L_ {1}}$${\ displaystyle \ Sigma _ {1}}$${\ displaystyle L_ {2}}$${\ displaystyle \ Sigma _ {2}}$${\ displaystyle \ Sigma _ {1} \ cup \ Sigma _ {2}}$${\ displaystyle (\ Sigma _ {1} \ cup \ Sigma _ {2}) ^ {*}}$

• Uniunea ${\ displaystyle L_ {1} \ cup L_ {2}}$
• media ${\ displaystyle L_ {1} \ cap L_ {2}}$
• diferența ${\ displaystyle L_ {1} \ setminus L_ {2}}$

Limbi despre . ${\ displaystyle \ Sigma _ {1} \ cup \ Sigma _ {2}}$

Alte operațiuni privind limbile sunt:

Concatenare

Concatenarea a două limbi și este limba de cuvinte care este creat scriind un cuvânt după altul ( concatenarea ) de la și de la : ${\ displaystyle L_ {1}}$${\ displaystyle L_ {2}}$${\ displaystyle u}$${\ displaystyle L_ {1}}$${\ displaystyle v}$${\ displaystyle L_ {2}}$

${\ displaystyle L_ {1} \ circ L_ {2}: = \ {uv \ mid u \ in L_ {1}, v \ in L_ {2} \}}$.

De exemplu, concatenările diferitelor limbi de deasupra alfabetului sunt : ${\ displaystyle \ Sigma = \ {a, \, b \}}$

${\ displaystyle \ {a \} \ circ \ {ab \} = \ {aab \}}$

${\ displaystyle \ {a, \, bb \} \ circ \ {aa, \, b \} = \ {aaa, \, ab, \, bbaa, \, bbb \}}$

${\ displaystyle \ {abb, \, bab \} \ circ \ {\ varepsilon, \, aab, \, bb \} = \ {abb, \, bab, \, abbaab, \, babaab, \, abbbb, \ , babbb \}}$

Elementul neutru al concatenării este limbajul, care conține doar cuvântul gol . Următoarele se aplică oricărei limbi : ${\ displaystyle L}$

${\ displaystyle L \ circ \ {\ varepsilon \} = \ {\ varepsilon \} \ circ L = L}$

Elementul absorbant al concatenării este un limbaj gol, astfel încât pentru fiecare limbă : ${\ displaystyle L \ subseteq \ Sigma ^ {*}}$

${\ displaystyle L \ circ \ {\} = \ {\} \ circ L = \ {\}}$

Concatenarea limbilor, ca și concatenarea cuvintelor, este asociativă , dar nu comutativă . De exemplu:

${\ displaystyle (\ {a, \, bab \} \ circ \ {a, \, b \}) \ circ \ {ab \} = \ {a, \, bab \} \ circ (\ {a, \ , b \} \ circ \ {ab \}) = \ {aaab, \, abab, \, babaab, \, babbab \}}$

dar:

${\ displaystyle \ {a, \, bab \} \ circ \ {a, \, b \} = \ {aa, \, ab, \, baba, \, babb \} \ not = \ {aa, \, abab, \, ba, \, bbab \} = \ {a, \, b \} \ circ \ {a, \, bab \}}$

În plus, din moment ce setul de alimentare al anvelopei Kleen lui a oricărui alfabet (care este egală cu mulțimea tuturor limbilor care pot fi formate din ) este închis în raport cu concatenare, aceasta formează un monoid împreună cu concatenarea ca operator și limba a cuvântului gol ca element neutru . ${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma}$

putere

Puterea unei limbi este concatenarea a acestei limbi de ori cu ea însăși este definit recursiv cu.: ${\ displaystyle L ^ {n}}$${\ displaystyle n}$

${\ displaystyle L ^ {0}: = \ {\ varepsilon \}}$

${\ displaystyle L ^ {n + 1}: = L ^ {n} \ circ L}$   (pentru )${\ displaystyle n \ in \ mathbb {N} _ {0}}$

De exemplu:

${\ displaystyle \ lbrace aa, \, abab, \, bbab, \, ba \ rbrace ^ {0} = \ lbrace \ varepsilon \ rbrace}$

${\ displaystyle \ lbrace a, \, b \ rbrace ^ {2} = \ lbrace a, \, b \ rbrace ^ {1} \, \ circ \, \ lbrace a, \, b \ rbrace = (\ lbrace a , \, b \ rbrace ^ {0} \, \ circ \, \ lbrace a, \, b \ rbrace) \, \ circ \, \ lbrace a, \, b \ rbrace = (\ lbrace \ varepsilon \ rbrace \ , \ circ \, \ lbrace a, \, b \ rbrace) \, \ circ \, \ lbrace a, \, b \ rbrace = \ lbrace aa, \, ab, \, ba, \, bb \ rbrace}$

${\ displaystyle \ lbrace a \ rbrace ^ {4} = \ lbrace a \ rbrace \, \ circ \, \ lbrace a \ rbrace \, \ circ \, \ lbrace a \ rbrace \, \ circ \, \ lbrace a \ rbrace = \ lbrace aaaa \ rbrace}$

În special, următoarele se aplică fiecărui limbaj formal unic (cu ) și fiecare : ${\ displaystyle L = \ lbrace w \ rbrace}$${\ displaystyle w \ in \ Sigma ^ {\ ast}}$${\ displaystyle n \ in \ mathbb {N} _ {0}}$

${\ displaystyle L ^ {n} = \ lbrace w \ rbrace ^ {n} = \ lbrace w ^ {n} \ rbrace}$

Kleene - * - grad și Kleene - + - grad

Kleene - * - închidere (plic Kleene, de asemenea , numit repetare ) și Kleene - + - închiderea (plic pozitiv) al unui limbaj formal sunt definite prin unirea limbilor de putere : ${\ displaystyle L ^ {*}}$ ${\ displaystyle L ^ {+}}$${\ displaystyle L}$${\ displaystyle L}$

${\ displaystyle L ^ {*}: = \ bigcup _ {i \ in \ mathbb {N} _ {0}} L ^ {i}}$

 

${\ displaystyle L ^ {+}: = \ bigcup _ {i \ in \ mathbb {N}} L ^ {i}}$

Cursuri importante de limbaj formal

1. În 1956, Noam Chomsky a stabilit o ierarhie a gramaticilor formale care produc diferite tipuri de limbaje formale. Acest lucru este cunoscut astăzi ca ierarhia Chomsky . Se face distincția între tipul 0, tipul 1, tipul 2 și tipul 3: limbaje recursive enumerabile , sensibile la context , fără context și limbaje obișnuite .
2. Aristid Lindenmayer a propus un sistem de control în care etapele de înlocuire sunt efectuate în paralel la fiecare pas, la fiecare punct. Aceste sisteme se numesc sisteme Lindenmayer .
3. Cu sistemele semi-Thue , pot fi setate limbi, care sunt derivate din cuvinte de pornire.
4. Cu sistemele Church-Rosser, limbajele explică cuvintele lor să fie reduse la un cuvânt terminal.
5. Sistemele de rescriere a termenilor generează setul de termeni care sunt echivalenți cu un termen de pornire.
6. Obținem generalizări ale limbajelor formale cu gramaticile grafice cu ajutorul cărora putem genera limbaje grafice.
7. Gramaticile hipergrafului produc hipergrafe , o generalizare a graficelor.

Istoric

Scrierea conceptuală a lui Gottlob Frege este considerată a fi una dintre primele limbaje formale , una cum Frege a scris „limbajul formulelor gândirii pure”. Sistemul Semi-Thue al lui Axel Thue , care a fost introdus în 1914 și poate fi folosit pentru a transforma corzi, a influențat, de asemenea, dezvoltarea gramaticilor formale.

Citat

Cercetările de bază de astăzi au fost stăpânite

Heinrich Scholz l-a cunoscut pe Konrad Zuse în 1944 , care lucra la calculul planului său ca parte a tezei sale de doctorat . În martie 1945, Scholz și-a exprimat aprecierea pentru aplicarea calculului său logic.

Vezi si

• limbaj construit
• Limbajul computerului
• Categorie: Limbaj formal - Listă de limbi formale

Aplicațiile vezi în:

• Teoria calculabilității
• Teoria complexității
• Criptografie
• Criptanaliza
• Construcția compilatorului

literatură

• Lars Peter Georgie: predictibilitate, complexitate, logică . Vieweg, Braunschweig / Wiesbaden,
  • O a treia ediție a apărut în 1995.
  • Ediție în limba engleză: Computabilitate, complexitate, logică . Publicat în seria: Studii în logică și bazele matematicii . Olanda de Nord, Amsterdam 1985.

O prezentare a limbajelor formale în contextul teoriei calculabilității, logicii și teoriei complexității. Face mari cereri cititorului, dar oferă informații profunde.

• Michael A. Harrison: Introducere în teoria limbajului formal . Publicat în seria: Series in Computer Science. Addison-Wesley, 1978.

O introducere foarte detaliată și foarte lăudată.

• John E. Hopcroft și Jeffrey D. Ullman : Introducere în teoria automatelor, limbaje formale și teoria complexității . Addison-Wesley, 1988.
  • Original în limba engleză: Introducere în teoria, limbile și calculul automatelor . Addison-Wesley, 1979.
  • O a treia ediție revizuită în limba germană a fost publicată în 1994 de Oldenbourg R. Verlag GmbH. În 2004, Addison-Wesley a publicat a doua ediție revizuită.

Originalul în limba engleză este cea mai citată carte din domeniul informaticii teoretice. Dovezile sunt denaturate ocazional în traducerile mai vechi în germană. Această carte a fost tradusă în numeroase limbi.

• Grzegorz Rozenberg și Arto Salomaa: Teoria matematică a L-Systems . Academic Press, New York 1980.

Cea mai detaliată carte despre sistemele L.

• Grzegorz Rozenberg și Arto Salomaa (editori): Manual de limbi formale . Volumul I-III, Springer, 1997, ISBN 3-540-61486-9 .

O prezentare detaliată a celor mai importante domenii ale limbajelor formale este prezentată de academicienii care sunt activi în acest domeniu.

• Arto Salomaa: Limbi formale . Springer, 1978.
  • Original englez: Limbi formale . Academic Press, 1973.
• Ingo Wegener: Informatică teoretică . Teubner, Stuttgart 1993, ISBN 3-519-02123-4 .

În reprezentarea limbajelor formale, complexitatea construcțiilor limbajului formal este întotdeauna tratată. În caz contrar, acest lucru poate fi găsit doar în literatura originală.

• U. Hedtstück: Introducere în informatica teoretică - Limbaje formale și teoria automatelor . Oldenbourg Verlag, München 2000, ISBN 3-486-25515-0 .
• S. Abramsky, Dov M. Gabbay, TSE Maibaum (eds.): Manual de logică în informatică. Vol. 5: Metode logice și algebrice. Oxford University Press 2000, ISBN 0-19-853781-6 .
• Mogens Nielsen, Wolfgang Thomas: Logică în informatică. Springer 1998, ISBN 3-540-64570-5

Dovezi individuale

1. ↑ Chomsky, Noam (1956). „Trei modele pentru descrierea limbajului”. Tranzacții IRE privind teoria informației (2): 113-124.
2. ↑ Martin Davis (1995). Influențele logicii matematice asupra informaticii. În Rolf Herken. Mașina universală Turing: o anchetă de jumătate de secol. Săritor. P. 290. ISBN 978-3-211-82637-9 .
3. ^ Ronald V. Book, Friedrich Otto: Sisteme de rescriere a șirurilor. Springer, 1993, ISBN 0-387-97965-4 , p. 36.
4. ↑ În: Cercetare și progres nr. 35/36, anul 1941, p. 382 și urm.
5. ↑ Hartmut Petzold : Aritmetici moderni. Industrializarea tehnologiei informatice în Germania. CH Beck Verlag, München 1992.