Viquipèdia

Llenguatge formal: diferència entre les revisions

Exploració interactiva de l'historial
← Edició anteriorEdició següent →
Contingut suprimit Contingut afegit
VisualWikitext
Nova plantilla de navegació
Etiqueta: editor de codi 2017
m Tipografia
Línia 25:
Es poden utilitzar diverses operacions per a produir nous llenguatges a partir d'altres daus. Suposem que '' L '' <sub> 1 </sub> i '' L '' <sub> 2 </sub> són llenguatges sobre un alfabet comú. Llavors:
 
* La ''concatenació'' ''L''<sub>1</sub>''V''<sub>2</sub>₂ consisteix en totes aquelles paraules de la manera ''vw'' on ''v'' és una paraula de ''L''<sub>1</sub> i ''w'' és una paraula de ''L''<sub>2</sub>₂
* La ''intersecció'' ''L''<sub>1</sub> & ''L''<sub>2</sub>₂ consisteix en totes aquelles paraules que estan contingudes tant en ''L''<sub>1</sub> com en ''L''<sub>2</sub>₂
* La ''unió'' ''L''<sub>1</sub>|''L''<sub>2</sub>₂ consisteix en totes aquelles paraules que estan contingudes ja sigui en ''L''<sub>1</sub> o en ''L''<sub>2</sub>₂
* El ''complement'' ~ ''L''<sub>1</sub> consisteix en totes aquelles paraules produïdes sobre l'alfabet de ''L''<sub>1</sub> que no estan ja contingudes en ''L''<sub>1</sub>
* El ''quocient'' ''L''<sub>1</sub>/''L''<sub>2</sub>₂ consisteix en totes aquelles paraules ''v'' per a les quals hi ha una paraula ''w'' a ''L''<sub>2</sub>₂ tals que ''vw'' es troba en ''L''<sub>1</sub>
* L'''estrella'' ''L''<sub>1</sub><sup>*</sup> consisteix en totes aquelles paraules que poden ser escrites de la manera ''W''<sub>1</sub>''W''<sub>2</sub>₂...''W''<sub>n</sub> on tot ''W''<sub>i</sub> es troba en ''L''<sub>1</sub> i n≥0. (Noteu que aquesta definició inclou ε en qualsevol ''L''*)
* La ''intercalació'' ''L''<sub>1</sub>*''L''<sub>2</sub>₂ consisteix en totes aquelles paraules que poden ser escrites de la manera ''v''<sub>1</sub>''w''<sub>1</sub>''v''<sub>2</sub>₂''w''<sub>2</sub>₂...''v''<sub>n</sub>''w''<sub>n</sub>; són paraules tals que la concatenació ''v''<sub>1</sub>...''v''<sub>n</sub> és a ''L''<sub>1</sub>, i la concatenació ''w''<sub>1</sub>...''w''<sub>n</sub> és a ''L''<sub>2</sub>₂
 
Una pregunta que es fa típicament sobre un determinat llenguatge formal ''L'' és com és de difícil decidir si inclou o no una determinada paraula ''v''. Aquest tema és del domini de la [[teoria de la computabilitat]] i la [[teoria de la complexitat computacional]].
Obtingut de «https://ca.wikipedia.org/wiki/Llenguatge_formal»