Llenguatge lliure de context

En matemàtiques, lògica i complexitat computacional un llenguatge formal és un llenguatge lliure de context si es pot generar amb una gramàtica lliure de context.[1]

El conjunt de tots els llenguatges lliures de context és idèntic al conjunt de llenguatges acceptats per un autòmat amb pila, cosa que fa aquests llenguatges adequats per analitzar sintàcticament (parser).

A més, donada una gramàtica lliure de context, hi ha una forma directa de generar un autòmat amb pila per dita gramàtica i el seu corresponent llenguatge. L'operació contraria no és directe.

Diferents gramàtiques lliures de context poden generar el mateix llenguatge lliure de context.

Propietats de clausura

Els llenguatges lliures de context son tancats segons les següents operacions. Sigui L i P dos llenguatges lliures de context, el llenguatge resultat també ho es:

  • la unió
  • l'invers de L
  • la concatenació
  • la clausura de Kleene
  • la imatge sota un homomorfisme
  • la imatge sota un homomorfisme
  • el desplaçament circular d'L (el llenguatge )
  • la clausura prefix d'L (el conjunt de tots els prefixos d'L)
  • el quocient L/R d'L per un llenguatge regular R

Aquesta classe de llenguatges no son tancats per la intersecció, el complement ni la diferència. Tot i això, si L és un llenguatge lliure de context i D és un llenguatge regular, llavors la intersecció i la diferència son llenguatges lliures de context.

Referències

  1. ↑ Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790. 

Read other articles:

Resimen Württemberg

Seorang prajurit resimen Württemberg di akhir abad ke-18 Asrama resimen Württemberg di Semarang pada masa Hindia Belanda Resimen Württemberg (Jerman: Württembergisches Kapregimentcode: de is deprecated ) yang dikenal juga dengan Tentara Kontrakan adalah satu resimen berisi orang Jerman asal Württemberg yang dikontrak menjadi tentara Hindia Belanda pada tahun 1790-1808. Resimen Württemberg ini berjumlah 2.000 tentara. Pasukan ini dibawa ke Batavia oleh Karl Eugen, Adipati Württemberg pa...

 

Basilika Dua Puluh Enam Martir Suci Jepang, Nagasaki

Basilika Dua Puluh Enam Martir Suci JepangJepang: 日本二十六聖殉教者聖堂LokasiNagasakiNegaraJepangDenominasiGereja Katolik RomaSejarahDedikasi26 Martir JepangArsitekturStatusKon-katedral, basilika minorStatus fungsionalAktifGayaNeo-GotikSelesai1864AdministrasiKeuskupan AgungKeuskupan Agung Nagasaki Gereja Oura Tenshudo pada sebuah kartu pos lukisan tangan (era Meiji) Basilika Dua Puluh Enam Martir Suci Jepang[1] (日本二十六聖殉教者聖堂) juga Gereja Katedral O...

 

عائل (أحياء)

الجرذان السوداء مستودعات طبيعية للطاعون الدملي، إذ أن قمل الفئران الشرقي الذي يتغذى على هذه الفئران ناقلات لهذا المرض. في علم الأحياء والطب، العائل (أو المضيف) هو كائن حي يأوي ضيفًا طفيليًا أو متعايشًا أو متقايضًا (متكافلًا)، وعادةً ما يُزود الضيف بالغذاء والمسكن. تشمل الأ�...

Digulleville

Digulleville Sémaphore de Jardeheu, sur la pointe de Jardeheu, racheté par la commune en 2005. Administration Pays France Région Normandie Département Manche Arrondissement Cherbourg Intercommunalité CA du Cotentin Statut Commune déléguée Maire délégué Mandat Louis Cranois 2020-2026 Code postal 50440 Code commune 50163 Démographie Gentilé Digullevillais(es) Population 260 hab. (2020) Densité 33 hab./km2 Géographie Coordonnées 49° 41′ 56″ nord, 1�...

 

George Tenet

Questa voce o sezione sugli argomenti insegnanti statunitensi e politici statunitensi non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento. George Tenet 18° Direttore della CIADurata mandato15 dicembre 1996 - 11 luglio 2004 PredecessoreJohn M. Deutch SuccessorePorter Goss Dati generaliPartito politic...

 

Geography of East Timor

Geographical features of East Timor Geography of East TimorContinentAsiaRegionSoutheast Asia Lesser Sunda Islands Coordinates8°50′S 125°55′E / 8.833°S 125.917°E / -8.833; 125.917AreaRanked 154th • Total14,919 km2 (5,760 sq mi) • Land100% • Water0%Coastline706 km (439 mi)BordersIndonesia: 253 km (157 mi)Highest pointTatamailau (2,963 m or 9,721 ft)Lowest pointTimor Sea, Savu Sea, an...

Evaristo Frisoni

Questa voce sull'argomento calciatori italiani è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Evaristo Frisoni Nazionalità  Italia Calcio Ruolo Centrocampista Termine carriera 1941 - giocatore1942 - allenatore Carriera Giovanili  Brescia Squadre di club1 1925-1934 Brescia189 (32)1934-1938 Roma103 (4)1938-1941 Brescia78 (8) Carriera da allenatore 1938-1942 Brescia 1 I due...

 

キース・エマーソン

キース・エマーソンKeith Emerson 南カリフォルニアにて (2008年)基本情報生誕 (1944-11-02) 1944年11月2日出身地 イングランド ウェスト・ライディング・オブ・ヨークシャー、トッドモーデン死没 (2016-03-11) 2016年3月11日（71歳没）[1]ジャンル プログレッシブ・ロックロッククラシック音楽クラシック・ロックアート・ロック職業 ミュージシャンシンガーソングライターキー...

 

Steady Diet of Nothing

1991 studio album by FugaziSteady Diet of NothingStudio album by FugaziReleasedJuly 1, 1991RecordedJanuary–February 1991StudioInner Ear Studios (Arlington, Virginia)GenrePost-hardcoreLength36:20LabelDischordProducerFugaziFugazi chronology Repeater(1990) Steady Diet of Nothing(1991) In on the Kill Taker(1993) Steady Diet of Nothing is the second studio album by American post-hardcore band Fugazi, released in July 1991 by Dischord Records. Although a persistent rumor alleges that the ...

Secretary of State of Puerto Rico

Government of Puerto Rico This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Secretary of State of Puerto Rico – news · newspapers · books · scholar · JSTOR (December 2015) (Learn how and when to remove this message) Secretary of State of Puerto RicoOfficial sealIncumbentOmar Marrerosince July 12, 2021Depa...

 

CYP3A5

Enzyme involved in drug metabolism CYP3A5IdentifiersAliasesCYP3A5, CP35, CYPIIIA5, P450PCN3, PCN3, cytochrome P450 family 3 subfamily A member 5External IDsOMIM: 605325; MGI: 106099; HomoloGene: 133568; GeneCards: CYP3A5; OMA:CYP3A5 - orthologsGene location (Human)Chr.Chromosome 7 (human)[1]Band7q22.1Start99,648,194 bp[1]End99,679,998 bp[1]Gene location (Mouse)Chr.Chromosome 5 (mouse)[2]Band5 G2|5 85.17 cMStart145,373,119 bp[2]End145,406,533 bp[...

 

Tim nasional sepak bola Albania

AlbaniaJulukanKuq e Zinjtë (Merah dan Hitam)Shqiponjat (Elang)AsosiasiAsosiasi Sepak Bola AlbaniaKonfederasiUEFA (Eropa)Pelatih SylvinhoKaptenEtrit BerishaPenampilan terbanyakLorik Cana (93)Pencetak gol terbanyakRiza Lushta (30)Stadion kandangArena KombëtareKode FIFAALBPeringkat FIFATerkini 66 2 (4 April 2024)[1]Tertinggi22 (Agustus 2015)Terendah124 (Agustus 1997)Peringkat EloTerkini89 Warna pertama Warna kedua Warna ketiga Pertandingan internasional pertamaAlbania 2 - 3 Yugoslavia ...

Frank Tempel

Frank TempelMember of the German BundestagIn office2009–2017 Personal detailsBorn (1969-01-19) January 19, 1969 (age 55)Belzig, GermanyPolitical partyThe LeftChildren4OccupationPolitical Frank Tempel (born January 19, 1969) is a German politician (Die Linke). He was a member of the German Bundestag from 2009 to 2017, where he was the drug policy spokesman for the Bundestag parliamentary group from May 2010. In January 2014, Frank Tempel was elected unopposed as deputy chairman of the B...

 

Pandemi Covid-19 di Hawaii

Pandemi COVID-19 di HawaiiPeta penyebaran di Hawaii menurut persen orang yang terinfeksi (pada 11 Oktober)   10.00%+ terkonfirmasi terinfeksi   3.00%-10.00% terkonfirmasi terinfeksi   1.00%-3.00% terkonfirmasi terinfeksi   0.30%-1.00% terkonfirmasi terinfeksi   0.10%-0.30% terkonfirmasi terinfeksi   0.03%-0.10% terkonfirmasi terinfeksi   0.00%-0.03% terkonfirmasi terinfeksiPenyakitCOVID-19Galur virusSARS-CoV-2LokasiHawaii, ...

 

Neve

Disambiguazione – Se stai cercando altri significati, vedi Neve (disambigua). Questa voce o sezione sull'argomento scienza è priva o carente di note e riferimenti bibliografici puntuali. Sebbene vi siano una bibliografia e/o dei collegamenti esterni, manca la contestualizzazione delle fonti con note a piè di pagina o altri riferimenti precisi che indichino puntualmente la provenienza delle informazioni. Puoi migliorare questa voce citando le fonti più precisamente. Segui i suggerim...

Strada statale 7 dir/A del Tempio di Giove

Questa voce sugli argomenti strade d'Italia e Lazio è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Strada statale 7 dir/Adel Tempio di GioveLocalizzazioneStato Italia Regioni Lazio Province Latina DatiClassificazioneStrada statale InizioInnesto SS 7 (km 104+500) FineInnesto SS 213 Lunghezza1,484 km GestoreANAS Manuale La strada statale 7 dir/A del Tempio di Giove (SS 7 dir/A) è una strada statale italiana, diramazione della strada sta...

 

Dharmashala, Kannur

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Dharmashala, Kannur – news · newspapers · books · scholar · JSTOR (July 2016) (Learn how and when to remove this message) For other uses, see Dharamshala (disambiguation). Town in Kerala, IndiaDharmasalaTownEK Nayanar Memorial Govt. Woment and Children Hospita...

 

Wirtschafts- und Sozialrat der Vereinten Nationen

Wirtschafts- und Sozialrat der Vereinten NationenUnited Nations Economic and Social Council   Karte mit den aktuellen Mitgliedsstaaten des Wirtschafts- und Sozialrats Organisationsart Hauptorgan derVereinten Nationen Kürzel ECOSOC Leitung Chile Paula Narváez(79. Präsidentschaft; seit 27. Juli 2023)[1] Status aktiv Gegründet 26. Juni 1945 Hauptsitz New York City, New York,Vereinigte Staaten Vereinigte Staatenim jährlichen Wechsel mitGenf, Schweiz Schweiz Obero...

Pelote basque aux Jeux olympiques

Pelote basque aux Jeux olympiques Généralités Sport Pelote basque 1re apparition Paris, 1900 (Jeux d'été) Organisateur(s) Comité international olympique modifier Le Fronton de Neuilly aux JO 1900. Partie de pelote basque aux JO 1900. Pelote basque, deux équipes des JO 1900. L'unique épreuve de pelote basque aux Jeux olympiques s'est déroulée en 1900 à Paris, seulement 2 équipes y étaient inscrites. Le match n'a pas eu lieu mais le premier prix a été attribué à l'équipe espa...

 

Algebraic variety

Mathematical object studied in the field of algebraic geometry This article is about algebraic varieties. For the term variety of algebras, see Variety (universal algebra). The twisted cubic is a projective algebraic variety. Algebraic varieties are the central objects of study in algebraic geometry, a sub-field of mathematics. Classically, an algebraic variety is defined as the set of solutions of a system of polynomial equations over the real or complex numbers. Modern definitions generaliz...