Langage algébrique déterministe

En informatique théorique et en théorie des langages, un langage algébrique déterministe est un langage algébrique reconnu (par états finals) par un automate à pile déterministe. L'intérêt des langages déterministes est que leur analyse syntaxique se fait en temps linéaire en la longueur du mot, alors que dans un langage algébrique quelconque, la complexité est cubique, ou en tout cas se ramène à la complexité du produit matriciel, donc est en O(n^2,37) où n est la longueur du mot par l'algorithme de Valiant. Tout langage algébrique déterministe peut être décrit par une grammaire LR(1) et réciproquement. Cela permet de les utiliser pour des applications pratiques. Ainsi, la plupart des langages de programmation sont des langages algébriques déterministes.

Exemples

Le langage $\{a^{n}b^{n}\mid n\geq 0\}$ est déterministe.
Le langage $\{wcw^{r}\mid w\in \{a,b\}^{*}\}$ , où $c$ est une lettre différente de $a,b$ , et où $w^{r}$ est le retourné de $w$ , est déterministe.

Propriétés

La classe des langages algébriques déterministes contient strictement la classe des langages rationnels et est strictement incluse dans celle des langages algébriques, et même des langages algébriques inambigus.

Le contre-exemple type de langage algébrique non déterministe est l'ensemble des palindromes.

La classe des langages algébriques déterministes est close par complémentaire^[1]. Cependant :

elle n'est pas close par intersection (même contre-exemple que dans le cas non déterministe) ;
elle n'est pas close par union (conséquence de la clôture par complémentaire et union) ;
elle n'est pas close par concaténation ;
elle n'est pas close par miroir, par exemple, $\{ca^{n}b^{n}\}\cup \{da^{2n}b^{n}\}$ est algébrique déterministe mais pas $\{b^{n}a^{n}c\}\cup \{b^{n}a^{2n}d\}$ .

Exemples de langages non déterministes

Le langage $\{a^{n}b^{n}\mid n\geq 0\}\cup \{a^{n}b^{2n}\mid n\geq 0\}$ n'est pas déterministe.
Le langage $\{w\mid w=uv,|u|=|v|,|v|_{a}\geq 1\}$ n'est pas déterministe sur un alphabet à au moins deux lettres. Ce langage est formé des mots dont la deuxième moitié contient au moins une occurrence de la lettre $a$ .
Le langage des palindromes n'est pas déterministe^[2]^,^[3].

Le principe de construction de ces langages est le même : l'automate à pile doit prendre une décision sans connaître la totalité de la donnée ; dans le premier exemple, il doit anticiper si le nombre de b est égal au ou le double du nombre de a, dans le deuxième exemple, il doit tester la présence de la lettre a dans la deuxième moitié sans savoir s'il est déjà dans la deuxième moitié.

Il existe un lemme d'itération spécial pour les langages algébriques déterministes qui permet de prouver formellement qu'un langage n'est pas déterministe. L'énoncé est assez compliqué^[4]. Une variante de ce lemme, tout aussi compliquée, est donnée par Sheng Yu.

Notes et références

↑ Wolper 2006, Section 4.4.4, p. 97.
↑ Harrison 1978, Théorème 11.8.5..
↑ Michael Harrison montre même que ce langage n'est pas la réunion d'un nombre fini de langages déterministes.
↑ Harrison 1978, Théorème 11.8.3.

Bibliographie

(en) Michael A. Harrison, Introduction to Formal Language Theory, Reading, Mass., Addison-Wesley, 1978, 594 p. (ISBN 0-201-02955-3, OCLC 266962302)
Pierre Wolper, Introduction à la calculabilité : cours et exercices corrigés, Paris, Dunod, 2006, 3^e éd., 224 p. (ISBN 2-10-049981-5).
Sheng Yu, « A pumping lemma for deterministic context-free languages », Information Processing Letters, vol. 31, n^o 1,‎ 1989, p. 47–51 (DOI 10.1016/0020-0190(89)90108-7)

v · m

Théorie des automates, des langages formels et des grammaires formelles

Hiérarchie de Chomsky	Grammaire	Langage	Automate
Type-0	Grammaire sans restriction	Langage récursivement énumérable Langage récursif	Machine de Turing Machine de Turing qui s'arrête toujours
Type-1	Grammaire contextuelle Grammaire indexée Grammaire d'arbres adjoints	Langage contextuel Langage indexé Grammaire d'arbres adjoints	Automate linéairement borné Automate à piles emboîtées Automate à piles intégrées
Type-2	Grammaire non contextuelle ou grammaire algébrique Grammaire non contextuelle déterministe	Langage non contextuel ou langage algébrique Langage algébrique déterministe Langage à pile visible	Automate à pile Automate à pile déterministe Automate à pile visible
Type-3	Grammaire régulière ou grammaire rationnelle	Langage rationnel Langage sans étoile	Automate fini déterministe Monoïde syntaxique apériodique

Portail de l'informatique théorique

Read other articles:

Antibakteri

Antibakteri adalah zat yang dapat mengganggu pertumbuhan atau bahkan mematikan bakteri dengan cara mengganggu metabolisme mikrob yang merugikan.[1] Mikroorganisme dapat menyebabkan bahaya karena kemampuan menginfeksi dan menimbulkan penyakit serta merusak bahan pangan. Antibakteri termasuk kedalam antimikroba yang digunakan untuk menghambat pertumbuhan bakteri.[2] Kriteria Antibakteri hanya dapat digunakan jika mempunyai sifat tosik selektif, artinya dapat membunuh bakteri yan...

Kenta Mukuhara

Kenta Mukuhara Informasi pribadiNama lengkap Kenta MukuharaTanggal lahir 6 Juli 1989 (umur 34)Tempat lahir Tokyo, JepangPosisi bermain BekKarier senior*Tahun Tim Tampil (Gol)2008-2014 FC Tokyo 2013 →Cerezo Osaka 2015- Cerezo Osaka * Penampilan dan gol di klub senior hanya dihitung dari liga domestik Kenta Mukuhara (lahir 6 Juli 1989) adalah pemain sepak bola asal Jepang. Karier Kenta Mukuhara pernah bermain untuk FC Tokyo dan Cerezo Osaka. Pranala luar (Jepang) Profil dan statistik di...

Kayu Aro Barat, Kerinci

Kayu Aro BaratKecamatanNegara IndonesiaProvinsiJambiKabupatenKerinciPemerintahan • CamatAgus BagiyonoPopulasi • Total- jiwaKode Kemendagri15.01.19 Kode BPS1501092 Luas- km²Desa/kelurahan17 desa Kayu Aro Barat adalah sebuah kecamatan yang berada di Kabupaten Kerinci, Provinsi Jambi, Indonesia. Kecamatan ini dibentuk pada tahun 2012 dari pemekaran Kec. Kayu Aro.Berdiri pada tanggal 04 Mei 2012 berdasarkan Perda Kab.Kerinci No. 14/2012 . Pusat pemerintahan di Sungai...

Nippon Budokan

Nippon Budokan日本武道館BudokanLokasi2-3 Kitanomarukōen, Chiyoda, Tokyo 102-8321, JepangTransportasi umumTokyo Metro/Toei Subway (at Kudanshita): Templat:TSLS Toei Shinjuku Line Templat:TSLS Tozai Line Templat:TSLS Hanzomon LinePemilikThe Nippon Budokan FoundationKapasitas14,471Ukuran lapanganHeight: 42 m (140 ft)KonstruksiDidirikan1964Dibuka3 Oktober 1964; 59 tahun lalu (1964-10-03)Direnovasi2020Biaya2 miliar yen(5,6 juta dolar AS pada tahun 1964)ArsitekMamoru YamadaKont...

Sayur Matinggi, Tapanuli Selatan

Untuk tempat lain yang bernama sama, lihat Sayur Matinggi (disambiguasi). Sayur MatinggiKecamatanPeta lokasi Kecamatan Sayur MatinggiNegara IndonesiaProvinsiSumatera UtaraKabupatenTapanuli SelatanPemerintahan • CamatTaufik R. LubisPopulasi (2020)[1] • Total26.014 jiwa • Kepadatan88/km2 (230/sq mi)Kode pos22774Kode Kemendagri12.03.21 Kode BPS1203011 Luas295,11 km²Desa/kelurahan19 desa1 kelurahan Sayur Matinggi adalah sebuah kecamatan ...

Spring Creek, Nevada

CDP in Nevada, United StatesSpring Creek, NevadaCDPView of Spring Creek from E Mountain, with the Ruby Mountains in the backgroundLocation of Spring Creek within NevadaCoordinates: 40°44′48″N 115°35′34″W / 40.74667°N 115.59278°W / 40.74667; -115.59278CountryUnited StatesStateNevadaCountyElkoArea[1] • Total53.73 sq mi (139.17 km2) • Land53.67 sq mi (138.99 km2) • Water0.07 sq...

Pulau Sentosa

SentosaPulau di Singapura Looking south (top) and north (bottom) of Sentosa IslandJulukan: The State of FunLocation in SingaporeKoordinat: 1°14′53″N 103°49′48″E / 1.248°N 103.830°E / 1.248; 103.830Koordinat: 1°14′53″N 103°49′48″E / 1.248°N 103.830°E / 1.248; 103.830Negara SingaporePemerintahan • MayorSouth West CDC Low Yen Ling • Members of ParliamentWest Coast GRC Rachel Ong Sin Yen Lua...

Wang Mei-hua

Wang Mei-hua王美花Wang Mei-hua pada 2014 Wakil Menteri Urusan Ekonomi Republik TiongkokPetahanaMulai menjabat Juli 2016MenteriLee Chih-kungWakilShen Jong-chin Informasi pribadiLahirTanggal tidak terbaca. Angka tahun harus memiliki 4 digit (gunakan awalan nol untuk tahun < 1000). (usia Kesalahan ekspresi: Operator < tak terduga)TaiwanKebangsaanRepublik TiongkokSuami/istriWellington KooAlma materUniversitas Taiwan NasionalSunting kotak info • L • B Wang Mei-hua (Hanzi...

Phaistos Disc

Inscribed clay disc found in Crete, Greece Phaistos DiscPhaistos Disc, side A (top) and side B (bottom)MaterialClayCreated2nd millennium BCDiscoveredJuly 3, 1908Phaistos, Crete, GreeceDiscovered byLuigi PernierPresent locationHeraklion Archaeological Museum, Crete, Greece This article contains Phaistos Disc Unicode characters. Without proper rendering support, you may see question marks, boxes, or other symbols instead of Phaistos Disc glyphs. Palace complex at Phaistos The Phaistos Disc ...

2005 United Kingdom general election in Scotland

Main article: 2005 United Kingdom general election 2005 United Kingdom general election ← 2001 5 May 2005 (2005-05-05) 2010 → ← outgoing memberselected members →All 59 Scottish seats to the House of CommonsTurnout60.6%, 2.4% First party Second party Leader Tony Blair Charles Kennedy Party Labour Liberal Democrats Leader since 21 July 1994 9 August 1999 Last election 56 seats 10 seats Seats before 46 9 Sea...

Sybra sulcata

Sybra sulcata Klasifikasi ilmiah Kerajaan: Animalia Filum: Arthropoda Kelas: Insecta Ordo: Coleoptera Famili: Cerambycidae Subfamili: Lamiinae Tribus: Apomecynini Genus: Sybra Spesies: Sybra sulcata Sybra sulcata adalah spesies kumbang tanduk panjang yang berasal dari famili Cerambycidae. Spesies ini juga merupakan bagian dari genus Sybra, ordo Coleoptera, kelas Insecta, filum Arthropoda, dan kingdom Animalia. Larva kumbang ini biasanya mengebor ke dalam kayu dan dapat menyebabkan kerusakan ...

Jewel Box (star cluster)

Open cluster in the constellation Crux This article is about article is about the star cluster. For other uses, see Jewel box. Jewel BoxNGC 4755 taken by the VLT Credit: ESOObservation data (J2000 epoch)Right ascension12h 53m 42s[1]Declination−60° 22.0′[1]Distance6.44 kly[2] (1.968 kpc[3])Physical characteristicsMass– M☉Radius–Estimated age16 Myr[3]–Other designationsHerschel's Jewel Box,[1] Kappa Cr...

Crmnica

Crmnica numbered 16–22 in this map of Old Montenegro Crmnica (Serbian and Montenegrin: Црмница, pronounced [tsr̩mnitsa]) is one of the local communities (mjesne zajednice) of the municipality of Bar and a historical region in southern Montenegro. It was one of the four sub-regions of Old Montenegro, where it was known as Crmnička nahija (the nahija of Crmnica). Geography and demographics Crmnica is located in south-western Montenegro, between the historical area of the Paš...

List of Netflix original films (2018)

For Netflix original series and related specials, see List of Netflix original programming. For Netflix original stand-up comedy specials, see List of Netflix original stand-up comedy specials. For Netflix exclusive international distribution films, see Lists of Netflix exclusive international distribution programming. Netflix is an American global on-demand Internet streaming media provider, that has distributed a number of original programs, including original series, specials, miniseries,...

Киберкомандование США

Киберкомандование Соединённых Штатов Америкиангл. United States Cyber Command Эмблема Киберкомандования ВС США Годы существования 2009 год — по настоящее время Страна Соединённые Штаты Америки Подчинение Пентагон Входит в Стратегическое командование Вооружённых сил США Включа�...

UEFA EURO 2012

UEFA欧州選手権 > UEFA EURO 2012 UEFA EURO 2012大会概要開催国ポーランドウクライナ（2ヶ国共催）日程 2012年6月8日 - 7月1日チーム数 16 （UEFA連盟）開催地数 8 （8都市）大会結果優勝スペイン（3回目）準優勝イタリア3位ポルトガルドイツ大会統計試合数 31試合ゴール数 76点（1試合平均 2.45点）総入場者数 1,377,726人（1試合平均 44,443人）得点王フェルナ�...

Massacro del Bat Mitzvah

Massacro del Bat MitzvahattentatoData17 gennaio 2002 Stato Israele Coordinate32°26′17.61″N 34°55′31.79″E32°26′17.61″N, 34°55′31.79″E ResponsabiliAbdul Salaam Sadek Hassouneh (la Brigata dei Martiri di al-Aqsa rivendicò la responsabilità) ConseguenzeMorti7 (incluso l'attentatore) Feriti33 Modifica dati su Wikidata · Manuale Il massacro del Bat Mitzvah fu un attacco terroristico avvenuto ad Hadera, in Israele, il 17 gennaio 2002, in cui un uomo palestinese armat...

Archives départementales du Loiret

Cet article est une ébauche concernant le Loiret et le domaine des archives. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Archives départementales du Loiret L'ancien couvent des Minimes abrite les fonds anciens Informations générales Type Archives départementales Création 1796 Affiliation Conseil départemental Directrice Frédérique Hamm Ampleur 31 km Période dès 841 Bâtiment Bâtiment Ancien couve...

Danubian Principalities

Historical term for the eastern Balkan states of Moldavia and Wallachia 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: Danubian Principalities – news · newspapers · books · scholar · JSTOR (February 2011) (Learn how and when to remove this message) The Principalities of the Danube wider concept – Moldavia...

موندين

موندين الإحداثيات 39°54′48″N 97°32′19″W / 39.9133°N 97.5386°W / 39.9133; -97.5386 [1] تقسيم إداري البلد الولايات المتحدة[2] التقسيم الأعلى مقاطعة ريببليك خصائص جغرافية المساحة 0.518841 كيلومتر مربع (1 أبريل 2010) ارتفاع 498 متر عدد السكان عدد السكان 96 (...

/profillengkap.com/index.php/ar/العلاقات الكوستاريكية اللاوسية

/profillengkap.com/index.php/article/Dolaz cheese

Boeing B-29 Superfortress

Hialeah Market station

First Church of Christ, Scientist (Atlanta)