system
Răspunde în limba română, în stilul Wikipedia, cat mai corect gramatical.
user
Ce informații relevante ai despre Limbaj formal?
assistant
În matematică, logică și informatică, un limbaj formal este o mulțime de cuvinte de lungime finită (șiruri de caractere) bazate pe un alfabet finit, și teoria științifică ce tratează aceste entități se numește teoria limbajelor formale. Se poate  vorbi despre limbaje formale în multe contexte (științific, lingvistic, juridic, medical și altele) dar în acest articol tratează limbajele formale în sensul de limbaj studiat de teoria limbajelor formale.

Familiarizare 

Un exemplu de alfabet poate fi , și un șir peste acest alfabet ar putea fi . 

Un exemplu de limbaj peste acel alfabet și care conține șirul dat ca exemplu ar fi mulțimea tuturor șirurilor care conțin același număr de simboluri  și .

Cuvântul vid (adică șirul de lungime 0) este permis și este de obicei notat cu ,  sau .

Chiar dacă alfabetul este de lungime finită și lungimea oricărui cuvânt este finită, un limbaj poate avea un număr infinit de membri (pentru că mulțimea cuvintelor din el nu e limitată).

Exemple de limbaje 

Câteva exemple de limbaje formale:

 mulțimea tuturor cuvintelor peste alfabetul 
 mulțimea , unde n număr prim și  înseamnă  repetat de  ori 
 mulțimea programelor corecte din punct de vedere sintactic într-un limbaj de programare
 mulțimea intrărilor pentru care o mașină Turing se oprește.

Modalități de construcție 

Un limbaj formal poate fi specificat în mai multe feluri:

 Ca șiruri produse de o anumită gramatică formală (vezi ierarhia Chomsky);
 Șiruri produse de o expresie regulată;
 Șiruri acceptate de un automat, cum ar fi o mașină Turing sau un automat finit; 
 Dintr-o mulțime de întrebări de tip DA/NU, cele al căror răspuns este da - vezi problema deciziei.

Operații cu limbaje 

Se pot realiza operații pe limbaje pentru a obține alte limbaje din acestea. Să presupunem că  și  sunt două limbaje peste același alfabet.
 Concatenarea  (sau ) constă din toate șirurile de forma  unde  este un șir din  și  este un șir din .
 Intersecția  a lui  cu  constă din toate șirurile conținute atât în  cât și în .
 Reuniunea  a lui  și  constă din toate șirurile conținute în  sau în .
 Complementul limbajului  constă din toate șirurile peste alfabet care nu sunt conținute în .
 Diferența  a lui  și  constă din toate șirurile conținute în  dar nu și în .
 Câtul la dreapta  al lui  cu  constă din toate șirurile  pentru care există un șir  în  așa încât  este în .
 Închiderea Kleene  constă din toate șirurile de forma  cu șirurile  din  și . Aceasta include și șirul  deoarece acesta se obține pentru , care este o valoare permisă.
 Inversul  conține versiunile în oglindă ale tuturor șirurilor din .
 Amestecarea lui  și  constă din șirurile de forma  unde  și  sunt șiruri pentru care concatenarea  este din  și  sunt șiruri pentru care  este din .

O întrebare importantă pentru teoria limbajelor formale este "cât este de dificil să decidem dacă un cuvânt dat aparține unui limbaj?" Acesta este domeniul teoriei computabilității și teoriei complexității.

Legături externe 

 University of Maryland, Formal Language Definitions
 James Power, "Notes on Formal Language Theory and Parsing" , 29 November 2002. 

 Drafts of some chapters in the "Handbook of Formal Language Theory", Vol. 1-3, G. Rozenberg and A. Salomaa (eds.), Springer Verlag, (1997):t
 Alexandru Mateescu and Arto Salomaa, "Preface" in Vol.1, pp. v-viii, and "Formal Languages: An Introduction and a Synopsis", Chapter 1 in Vol. 1, pp.1-39
 Sheng Yu, "Regular Languages", Chapter 2 in Vol. 1
 Jean-Michel Autebert, Jean Berstel, Luc Boasson, "Context-Free Languages and Push-Down Automata", Chapter 3 in Vol. 1 
 Christian Choffrut and Juhani Karhumäki, "Combinatorics of Words", Chapter 6 in Vol. 1
 Tero Harju and Juhani Karhumäki, "Morphisms", Chapter 7 in Vol. 1, pp. 439 - 510
 Jean-Eric Pin, "Syntactic semigroups", Chapter 10 in Vol. 1, pp. 679-746
 M. Crochemore and C. Hancart, "Automata for matching patterns", Chapter 9 in Vol. 2
 Dora Giammarresi, Antonio Restivo, "Two-dimensional Languages", Chapter 4 in Vol. 3, pp. 215 - 267

Limbaje formale și automate