Llenguatge regular

Enmatemàtiques,lògicaicomplexitat computacionalunllenguatge formalés unllenguatge regularsi es pot expressar usantexpressions regulars.

També es pot definir un llenguatge regular com aquell que reconeix unautòmat finit.L'equivalència entre les expressions regulars i autòmats finits es demostra alteorema de Kleene.Aquest tipus de llenguatges s'etiqueten com de tipus 3 en lajerarquia de Chomskydels llenguatges formals.

Els llenguatges regulars son força útils en l'anàlisi d'entrades i el disseny dellenguatges de programació.

Definició formal

La col·lecció de llenguatges regulars sobre un alfabet Σ es defineix recursivament com:

• El llenguatge buit Ø i la cadena buida {ε} son llenguatges regulars.
• Per cadaa∈ Σ, el conjunt unitari {a} és un llenguatge regular.
• Si A i B son llenguatges regulars, llavorsA∪B(unió),A•B(concatenació), iA* (Clausura de Kleene) son llenguatges regulars.
• Cap altre llenguatge sobre Σ és regular.

VeieuExpressio regularper la seva sintaxi i semàntica.

Exemples

Tots els llenguatges finits son regulars. En particular el llenguatge buit {ε} = Ø és regular. Altres exemples típics consisteixen en el llenguatge format per totes les cadenes sobre un alfabet {a, b} que contenen un nombre parell deaso el llenguatge consistent en totes les cadenes de les formes: moltesas seguides de moltesbs.

Un exemple senzill d'un llenguatge que no és regular és el conjunt de cadenes tal que {aⁿbⁿ|n≥ 0 }. Intuïtivament es veu que no es pot reconèixer amb un autòmat finit, ja que té una memòria finita i no pot recordar el nombre exacte d'as.

Formalismes equivalents

Un llenguatge regular satisfà les següents propietats equivalents:

1. És el llenguatge d'unaexpressió regular.
2. És el llenguatge acceptat per unautòmat finit no determinista.
3. És el llenguatge acceptat per unautòmat finit determinista.
4. Es pot generar amb unagramàtica regular.
5. És el llenguatge acceptat per un autòmat finit alternant.
6. Es pot generar amb una gramàtica de prefix.
7. És el llenguatge acceptat per unamàquina de Turingde només lectura.
8. Es pot definir amblògica de segon ordre.

Propietats de clausura

Els llenguatges regulars son tancats segons vàries operacions. Si els llenguatgesKiLson regulars, també ho serà el resultat de les operacions següents:

• El conjunt d'operacions Booleanes:unióK∩L,interseccióK∩LicomplementariL
• Les operacions regularsK∪L,concatenacióK∘L,iclausura de KleeneL^*
• Operacions trio: homomorfisme de cadenes, la seva inversa i intersecció amb llenguatges regulars. Com a conseqüència, son tancats per operacions amb Transductor d'estats finits, com el quocientK/Lamb llenguatges regulars.
• La inversa L^R.Donat un autòmat finit no determinista que reconeix L, es pot obtenir un autòmat per reconèixer L^Rfent revertint totes les transicions i intercanviant l'estat inicial per l'estat final.

Problemes de decisió

Donats dos autòmats finits deterministes A i B, ésdecidiblesaber si accepten el mateix llenguatge.Com a conseqüència, usant les propietats de clausura, els següents problemes també son decidibles per qualsevol autòmat finit A i B, que accepten els llenguatgesL_AiL_Brespectivament:

• Inclusió:L_A⊆L_B?
• Disjunció:L_A∩L_B= {}?
• Buit:L_A= {}?
• Universalitat:L_A= Σ^*?
• Membre: donata∈ Σ^*,a∈L_B?

Per expressions regulars, el problema d'universalitat ésNP-completinclús per un alfabet simple.Per alfabets més grans, el problema ésPSPACE-complet.

Complexitat

Encomplexitat computacional,laclasse de complexitatde tots els llenguatges regulars s'anomena sovint com REGULAR o REG i és equivalent aDSPACE(O(1)), és a dir, el conjunt de problemes de decisió que es poden resoldre en espai constant (l'espai utilitzat és independent de la mida d'entrada).

REGULAR ≠AC⁰,ja que conté el problema de paritat de determinar si el nombre de bits a 1 a l'entrada és parell o senar, i aquest problema no està aAC⁰.

D'altra banda, REGULAR no contéAC⁰,ja que el llenguatge no regular dels palíndroms, o el llenguatge no regular$\{0^{n}1^{n}:n\in \mathbb {N} \}$es poden reconèixer perAC⁰.

Si un llenguatge es no regular, requereix que una màquina amb almenys espai Ω(log logn) per reconèixer-lo. Dit d'altra manera, la classeDSPACE(o(log log n)) és igual a la classe dels llenguatges regulars.

Posició a la jerarquia de Chomsky

Classes de llenguatges regulars dins la jerarquia de Chomsky

Per trobar la posició dels llenguatges regulars dins de lajerarquia de Chomskycal notar que tot llenguatge regular éslliure del context.A l'inrevés no és cert: per exemple el llenguatge consistent en totes les cadenes que tenen el mateix nombre d'as i debs és lliure del context però no és regular. Per provar que un llenguatge d'aquest tipus no és regular es fa servir elteorema de Myhill-Nerodeo elLema de bombament.

Els llenguatges regulars tenen subclasses força importants:

• Llenguatges finits: aquells llenguatges que contenen només un nombre finit de paraules (no confondre amb un llenguatge generat per un autòmat finit). Aquests llenguatges son regulars, ja que es poden crear amb una expressió regular que és la unió de cada paraula del llenguatge.
• Llenguatges lliures d'estrella, que es poden descriure amb una expressió regular construïda des del símbol buit, lletres,concatenaciói tots elsoperadors boolens,incloent-hi complement però no laclausura de Kleene.Aquesta classe inclou tots els llenguatges finits.