Limbaj formal

Prin limbaj formal , în matematică , logică , informatică și lingvistică , înțelegem un set de șiruri construite pe unalfabet , adică pe un set de obiecte practic simple care se numesc caractere, simboluri sau litere. De multe ori se presupune că alfabetul pe care este construit limba este un set finit.

Istorie

Primul limbaj formal despre care știm este introdus de Gottlob Frege în Begriffsschrift (1879), tradus în italiană ca „Ideografie” și pe care subtitlul îl definește ca „un limbaj în formulele gândirii pure, în imitarea celei aritmetice”.

Teoria limbajelor formale s-a născut în anii 1950 în domeniul lingvisticii, ca mod de a înțelege regularitățile limbilor naturale.

Descriere

Caracteristici

În mod formal, un limbaj L este definit ca $L\subseteq \Sigma ^{*}$ ${\ displaystyle L \ subseteq \ Sigma ^ {*}}$ $L \ subseteq \ Sigma ^ {{*}}$ , unde este $\Sigma ^{*}$ ${\ displaystyle \ Sigma ^ {*}}$ $\ Sigma ^ {{*}}$ (unde asteriscul indică steaua lui Kleene ) reprezintă ansamblul tuturor secvențelor finite ( șiruri sau cuvinte) care pot fi formate cu alfabetul $\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$ . Un limbaj poate fi de cardinalitate finită , infinită sau zero . Este important să rețineți că limba goală (notată cu $L=\emptyset$ ${\ displaystyle L = \ emptyset}$ $L = \ emptyset$ ) diferă de limba compusă exclusiv de șirul tăcut (sau cuvânt gol ), notat cu și , $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\ varepsilon$ sau $\lambda$ ${\ displaystyle \ lambda}$ $\ lambda$ .

De exemplu, având în vedere alfabetul $\Sigma =\left\{a,b\right\}$ ${\ displaystyle \ Sigma = \ left \ {a, b \ right \}}$ $\ Sigma = \ left \ {a, b \ right \}$ unele limbi posibile pe acest alfabet sunt:

Limbajul gol
$L=\left\{\varepsilon \right\}$ ${\ displaystyle L = \ left \ {\ varepsilon \ right \}}$ $L = \ left \ {\ varepsilon \ right \}$ (limba constând numai din șirul gol)
$L^{\prime }=\left\{ababba,aaabbbaaa,aaabbbabaababb\right\}$ ${\ displaystyle L ^ {\ prime} = \ left \ {ababba, aaabbbaaa, aaabbbabaababb \ right \}}$ $L ^ {{\ prime}} = \ left \ {ababba, aaabbbaaa, aaabbbabaababb \ right \}$ (limbaj finit)
$L^{\prime \prime }=a^{*}b^{*}$ ${\ displaystyle L ^ {\ prime \ prime} = a ^ {*} b ^ {*}}$ $L ^ {{\ prime \ prime}} = a ^ {{*}} b ^ {{*}}$ (limbaj infinit definit de o expresie regulată )
$L^{\prime \prime \prime }=\Sigma ^{*}$ ${\ displaystyle L ^ {\ prime \ prime \ prime} = \ Sigma ^ {*}}$ $L ^ {{\ prime \ prime \ prime}} = \ Sigma ^ {{*}}$

În general, vom spune că un model formal care poate recunoaște și genera toate și numai șirurile unui limbaj formal acționează ca o definiție a limbajului respectiv. Conform celor două abordări principale ale definiției limbajelor formale, un model poate fi concretizat într-o gramatică formală (abordare generativă) sau într-un automat (abordare de recunoaștere).

Definiția formal language

Un limbaj formal poate fi definit într-o mare varietate de moduri echivalente:

Setul de șiruri derivat dintr-o gramatică generativă
Setul de șiruri furnizat de o expresie regulată
Setul de corzi acceptat de un automat
Întrebări cu răspuns afirmativ, în contextul unei probleme de decizie , al cărui răspuns este de tip binar ( da / nu sau adevărat / fals )

Exemple de limbaje formale

Deși unele exemple de limbaje formale au fost definite mai sus, este posibil să se exprime unele limbaje formale pe $\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$ În felul următor:

Limba tuturor șirurilor care conțin același număr de a și b ;
Setul tuturor cuvintelor de pe $\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$ sau setul gol;
Setul de șiruri ale formei $a^{n}$ ${\ displaystyle a ^ {n}}$ $a ^ {{n}}$ cu n număr prim ;
Setul de programe într-un anumit limbaj de programare care se dovedesc a fi corecte din punct de vedere sintactic;
Setul de intrări care determină oprirea unei anumite mașini Turing

Operațiuni asupra limbajelor formale

Este posibil să se definească unele operații unare sau binare pentru a genera un nou limbaj din limbaje de date. Lasa-i sa fie $L_{1}$ ${\ displaystyle L_ {1}}$ $L_ {1}$ și $L_{2}$ ${\ displaystyle L_ {2}}$ $L_ {2}$ două limbi pe un alfabet dat.

$L=L_{1}\cdot L_{2}$ ${\ displaystyle L = L_ {1} \ cdot L_ {2}}$ $L = L_ {1} \ cdot L_ {2}$ este concatenarea sau juxtapunerea celor două limbi. Se compune din mulțimea tuturor siruri de caractere vw astfel încât $v\in L_{1}$ ${\ displaystyle v \ în L_ {1}}$ $v \ în L_ {1}$ Și $w\in L_{2}$ ${\ displaystyle w \ în L_ {2}}$ $w \ în L_ {2}$ .
$L=L_{1}\cap L_{2}$ ${\ displaystyle L = L_ {1} \ cap L_ {2}}$ $L = L_ {1} \ cap L_ {2}$ este intersecția dintre $L_{1}$ ${\ displaystyle L_ {1}}$ $L_ {1}$ și $L_{2}$ ${\ displaystyle L_ {2}}$ $L_ {2}$ . Se compune din setul tuturor șirurilor $w/w\in L_{1}\land w\in L_{2}$ ${\ displaystyle w / w \ în L_ {1} \ land w \ în L_ {2}}$ ${\ displaystyle w / w \ în L_ {1} \ land w \ în L_ {2}}$ , adică toate șirurile conținute în ambele $L_{1}$ ${\ displaystyle L_ {1}}$ $L_ {1}$ că în $L_{2}$ ${\ displaystyle L_ {2}}$ $L_ {2}$ .
$L=L_{1}\cup L_{2}$ ${\ displaystyle L = L_ {1} \ cup L_ {2}}$ $L = L_ {1} \ cup L_ {2}$ este uniunea dintre $L_{1}$ ${\ displaystyle L_ {1}}$ $L_ {1}$ și $L_{2}$ ${\ displaystyle L_ {2}}$ $L_ {2}$ . Se compune din setul tuturor șirurilor $w/w\in L_{1}\lor w\in L_{2}$ ${\ displaystyle w / w \ în L_ {1} \ lor w \ în L_ {2}}$ ${\ displaystyle w / w \ în L_ {1} \ lor w \ în L_ {2}}$ , adică toate șirurile care aparțin cel puțin uneia dintre cele două limbi.
$L={\bar {L}}_{1}$ ${\ displaystyle L = {\ bar {L}} _ {1}}$ $L = {\ bar {L}} _ {1}$ este complementul limbajului $L_{1}$ ${\ displaystyle L_ {1}}$ $L_ {1}$ . Se compune din toate corzile $w\in \Sigma ^{*}\setminus L_{1}$ ${\ displaystyle w \ in \ Sigma ^ {*} \ setminus L_ {1}}$ $w \ in \ Sigma ^ {{*}} \ setminus L_ {1}$ , adică toate șirurile de pe alfabet $\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$ care nu sunt conținute în $L_{1}$ ${\ displaystyle L_ {1}}$ $L_ {1}$ .
$L=L_{1}/L_{2}$ ${\ displaystyle L = L_ {1} / L_ {2}}$ $L = L_ {1} / L_ {2}$ este coeficientul corect al $L_{1}$ ${\ displaystyle L_ {1}}$ $L_ {1}$ din $L_{2}$ ${\ displaystyle L_ {2}}$ $L_ {2}$ . Se compune din toate șirurile v pentru care există un w în șir $L_{2}$ ${\ displaystyle L_ {2}}$ $L_ {2}$ astfel încât $vw\in L_{1}$ ${\ displaystyle vw \ în L_ {1}}$ $vw \ în L_ {1}$ .
$L=L_{1}^{*}$ ${\ displaystyle L = L_ {1} ^ {*}}$ $L = L_ {1} ^ {{*}}$ este vedeta lui Kleene . Se compune din limbaj $\bigcup _{n\in \mathbb {N} }L_{1}^{n}$ ${\ displaystyle \ bigcup _ {n \ in \ mathbb {N}} L_ {1} ^ {n}}$ $\ bigcup _ {{n \ in \ mathbb {N}}} L_ {1} ^ {{n}}$ , adică toate șirurile de formă $w_{1}w_{2}\cdots w_{n}$ ${\ displaystyle w_ {1} w_ {2} \ cdots w_ {n}}$ $w_ {1} w_ {2} \ cdots w_ {n}$ astfel încât $w_{i}/w_{i}\in L_{1}\land 0\leq i\leq n$ ${\ displaystyle w_ {i} / w_ {i} \ în L_ {1} \ land 0 \ leq i \ leq n}$ ${\ displaystyle w_ {i} / w_ {i} \ în L_ {1} \ land 0 \ leq i \ leq n}$ . Atâta timp cât $L_{1}^{0}={\varepsilon }$ ${\ displaystyle L_ {1} ^ {0} = {\ varepsilon}}$ $L_ {1} ^ {{0}} = {\ varepsilon}$ șirul se schimbă $\varepsilon \in L$ ${\ displaystyle \ varepsilon \ în L}$ $\ varepsilon \ în L$ .
$L=L_{1}^{R}$ ${\ displaystyle L = L_ {1} ^ {R}}$ $L = L_ {1} ^ {{R}}$ este reflexia . De sine $w=a_{1}a_{2}\cdots a_{n}$ ${\ displaystyle w = a_ {1} a_ {2} \ cdots a_ {n}}$ $w = a_ {1} a_ {2} \ cdots a_ {n}$ Și $w^{R}=a_{n}a_{n-1}\cdots a_{1}$ ${\ displaystyle w ^ {R} = a_ {n} a_ {n-1} \ cdots a_ {1}}$ $w ^ {{R}} = a_ {n} a _ {{n-1}} \ cdots a_ {1}$ , limba L conține toate șirurile $w_{R}/w\in L_{1}$ ${\ displaystyle w_ {R} / w \ în L_ {1}}$ $w _ {{R}} / w \ în L_ {1}$ , adică toate șirurile reflectate de $L_{1}$ ${\ displaystyle L_ {1}}$ $L_ {1}$ .
Amestecarea sau amestecarea de $L_{1}$ ${\ displaystyle L_ {1}}$ $L_ {1}$ și $L_{2}$ ${\ displaystyle L_ {2}}$ $L_ {2}$ constă din toate șirurile care pot fi scrise în formă $v_{1}w_{1}v_{2}w_{2}\cdots v_{n}w_{n}$ ${\ displaystyle v_ {1} w_ {1} v_ {2} w_ {2} \ cdots v_ {n} w_ {n}}$ $v_ {1} w_ {1} v_ {2} w_ {2} \ cdots v_ {n} w_ {n}$ astfel încât $n\geq 1\land \left\{v_{1}\cdots v_{n}\right\}\in L_{1}\land \left\{w_{1}\cdots w_{n}\right\}\in L_{2}$ ${\ displaystyle n \ geq 1 \ land \ left \ {v_ {1} \ cdots v_ {n} \ right \} \ în L_ {1} \ land \ left \ {w_ {1} \ cdots w_ {n} \ dreapta \} \ în L_ {2}}$ ${\ displaystyle n \ geq 1 \ land \ left \ {v_ {1} \ cdots v_ {n} \ right \} \ în L_ {1} \ land \ left \ {w_ {1} \ cdots w_ {n} \ dreapta \} \ în L_ {2}}$ .

Una dintre cele mai frecvente probleme legate de limbile formale se referă la problema apartenenței . Având un șir w și un limbaj L, verificați dacă $w\in L$ ${\ displaystyle w \ în L}$ $w \ în L$ este o problemă care implică atât teoria calculabilității, cât și teoria complexității .

Bibliografie

(EN) Limbaje formale , în Encyclopedia of Computer Science, Hoboken, Wiley, 2003.
( EN ) John E. Hopcroft , Rajeev Motwani; Jeffrey D. Ullman , Limbi , în Introducere în teoria automatelor, limbi și calcul , Addison Wesley, 15 iulie 2006, ISBN 978-0-321-46225-1 .

Elemente conexe

Alte proiecte

Wikiversitatea conține resurse privind limbajul formal
Wikimedia Commons conține imagini sau alte fișiere cu limbaj formal

linkuri externe

( EN ) Limbaj formal , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.

Teoria automatelor : limbaje formale și gramatici formale
Ierarhia Chomsky	Gramatica formală	Limba	Automat minim
Tipul-0	(nelimitat)	Recursiv enumerabil	Mașină Turing
	(nelimitat)	Recursiv	Decider
Tipul 1	Context dependent	Context dependent	Automat liniar
Tipul 2	Fără context	Fără context	Automat cu baterie ND
Tipul 3	Regulat	Regulat	Stări finite
Fiecare categorie de limbă sau gramatică este un subset adecvat al categoriei imediat deasupra acesteia.

Controlul autorității	Tesauro BNCF 5999 · LCCN (EN) sh85050802 · GND (DE) 4017848-1 · BNF (FR) cb11967270h (dată) · NDL (EN, JA) 00.576.869

Portal IT

Portalul de matematică