Lenguaje sensible al contexto

En las ciencias de la computación, un lenguaje sensible al contexto es un lenguaje formal que puede ser definido por gramáticas sensibles al contexto. Es uno de los cuatro tipos de gramáticas en la jerarquía de Chomsky, siendo esta gramática la menos frecuente, tanto en la teoría como en la práctica.

Propiedades computacionales

Computacionalmente, un lenguaje sensible al contexto es equivalente a una máquina de Turing no determinista linealmente acotada, también llamado Autómata linealmente acotado. Se trata de una máquina de Turing no determinista con una cinta de sólo kn posiciones, donde n es el tamaño de la entrada y k es la constante asociada a la máquina. Esto significa que cada lenguaje formal que puede ser decidido por una máquina es un lenguaje sensible al contexto.

Ejemplos

Un ejemplo de un lenguaje sensible al contexto que no es libre de contexto es
L = {aⁿbⁿcⁿ | n>= 0} no es un lenguaje libre de contexto, pero si es un lenguaje sensible al contexto. Una gramática para L:

Transiciones
S → ε	aB → ab
S → aSBC	bB → bb
CB → HB	bC → bc
HB → HC	cC → cc
HC → BC

L puede demostrarse como un lenguaje sensible al contexto mediante la construcción de un autómata lineal acotado que acepta L. Se puede demostrar fácilmente que este lenguaje no es ni regular, ni independiente del contexto, por la aplicación del Lema del bombeo. Un ejemplo de un lenguaje recursivo que no es sensible al contexto es cualquier lenguaje recursivo cuya decisión es un problema EXPSPACE-hard, por ejemplo, el conjunto de pares equivalentes de expresiones regulares con exponenciación.

Propiedades

La unión, intersección, y concatenación de dos Lenguajes sensibles al contexto es un Lenguaje sensible al contexto.
El complemento de un lenguaje sensible al contexto es en sí mismo sensible al contexto.
Cada gramática libre de contexto es un lenguaje sensible al contexto.
La composición de una cadena en un lenguaje definido por una gramática sensible al contexto arbitraria, o por una gramática determinista sensible al contexto arbitraria, es un problema PSPACE-completo.

Véase también

Referencias

Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
Traducido de , exactamente la versión http://en.wikipedia.org/wiki/Context-sensitive_language, bajo licencia GFDL y CC-CI 3.0
Immerman, Neil (1988). «Nondeterministic space is closed under complementation». SIAM J. Comput. 17 (5): 935-938. doi:10.1137/0217058.

Datos: Q1430282

Read other articles:

Formula Rossa

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Januari 2023. Formula Rossa adalah roller coaster yang terletak di Ferrari World Abu Dhabi, Uni Emirat Arab. Formula Rossa dibuka untuk umum pada November 2010. Saat ini Formula Rossa adalah roller coaster tercepat di dunia dengan kecepatan maksimal 240 km / ja...

2022 AFF Championship qualification

Football match2022 AFF Championship qualification Brunei Timor-Leste 6 3 First leg Brunei Timor-Leste 6 2 Date5 November 2022 (2022-11-05)VenueTrack & Field Sports Complex, Bandar Seri Begawan, BruneiRefereeWarintorn Sassadee (Thailand)Second leg Timor-Leste Brunei 1 0 Date8 November 2022 (2022-11-08)VenueTrack & Field Sports Complex, Bandar Seri Begawan, BruneiRefereeRazlan Joffri Ali (Malaysia)← 2018 2024 → The 2022 AFF Championship qualific...

KSJT-FM

For the San Angelo, Texas, United States airport, see Mathis Field. Radio station in San Angelo, TexasKSJT-FMKSJT StudiosSan Angelo, TexasBroadcast areaSan AngeloFrequency107.5 MHzBrandingLa Grande 107.5ProgrammingLanguage(s)SpanishFormatSpanish musicOwnershipOwnerLa Unica Broadcasting Co.Sister stationsKPTJHistoryCall sign meaningK, SJT- aeronautical call signTechnical informationFacility ID36186ClassC1ERP100,000 wattsHAAT184.0 meters (603.7 ft)Transmitter coordinates31°26′19.00″N ...

Zeni

Anggota zeni Polandia di Pakistan.Zeni (bahasa Belanda: genie; bahasa Inggris: combat engineer, pioneer, atau sapper) adalah satuan militer yang melakukan tugas-tugas teknik militer untuk mendukung operasi tempur pasukan darat. Insinyur tempur melakukan berbagai tugas teknik militer, perang terowongan, perang ranjau serta konstruksi dan pembongkaran di dalam dan di luar zona pertempuran.[1][2] Pasukan zeni memfasilitasi mobilitas pasukan kawan dan menghambat pergerakan musuh. ...

Chakkikotha Chankaran

1989 Indian filmChakkikotha ChankaranPosterDirected byKrishnakumarWritten byVR GopalakrishnanProduced byGoodKnight FilmsStarringJayaram Nedumudi Venu Urvashi Geetha Thilakan SukumariCinematographyVijayakumarEdited byA. Paul Durai SinghamMusic byShankar–GaneshRelease date1989CountryIndiaLanguageMalayalam Chakkikotha Chankaran is 1989 Malayalam comedy film, directed by Krishnakumar, starring Jayaram and Urvashi.[1] The movie is heavily inspired by the 1987 Tamil movie Enga Veettu Ram...

Attorney General of New Hampshire

Attorney General of New HampshireIncumbentJohn Formellasince April 22, 2021New Hampshire Department of JusticeTypeAttorney GeneralAppointerGovernor of New Hampshirewith approval of the Governor's CouncilTerm length4 yearsConstituting instrumentPart II, Article 46 of the Constitution of New HampshireFormation1892First holderEdwin G. EastmanSalary$141,390 (2022)Websitedoj.nh.gov Attorney general for the U.S. state of New Hampshire The Attorney General of New Hampshire is a constitutional o...

Voodoo Shoppe

2006 studio album by Cowboy MouthVoodoo ShoppeStudio album by Cowboy MouthReleasedFebruary 21, 2006 (2006-02-21)LabelEleven ThirtyProducerCowboy Mouth, Mike Mayeaux, Russ-T CobbCowboy Mouth chronology Uh-oh(2003) Voodoo Shoppe(2006) Fearless(2008) Professional ratingsReview scoresSourceRatingAllMusic[1]Village Voice(favourable)[2]PopMatters(7/10)[3]ARTISTdirect[4] Voodoo Shoppe is the tenth release and the seventh studio release of Cowboy...

Provinsi Bistriţa-Năsăud

Letak County Bistriţa-Năsăud di Rumania County Bistriţa-Năsăud merupakan sebuah county di Rumania yang memiliki luas wilayah 5.355 km² dan populasi 311.657 jiwa (2002). Ibu kotanya ialah Bistriţa. Pembagian administratif Provinsi Bistriţa-Năsăud memiliki 1 kotamadya, 3 kota kecil dan 56 komune. Kotamadya Bistriţa Kota kecil Beclean Năsăud Sângeorz-Băi Komune Bistriţa Bârgăului Braniştea Budacu de Jos Budeşti Căianu Mic Cetate Chiochiş Chiuza Ciceu-Giurgeşti Ciceu-...

Geography of Abkhazia

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: Geography of Abkhazia – news · newspapers · books · scholar · JSTOR (November 2013) (Learn how and when to remove this template message) This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help i...

Piala Negara-Negara Afrika 2023

artikel ini perlu dirapikan agar memenuhi standar Wikipedia. Tidak ada alasan yang diberikan. Silakan kembangkan artikel ini semampu Anda. Merapikan artikel dapat dilakukan dengan wikifikasi atau membagi artikel ke paragraf-paragraf. Jika sudah dirapikan, silakan hapus templat ini. (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini) Untuk turnamen wanita, lihat Piala Negara-Negara Afrika Wanita 2024. Artikel ini mendokumentasikan sebuah Africa Cup of Nations yang sedang berlan...

Crise de la dette publique grecque

Palais du parlement hellénique devant la place Syntagma à Athènes. La crise de la dette publique grecque est une crise financière ayant débuté en 2008, affectant la Grèce et menaçant de s'étendre à l'Union européenne, due à l'emballement de la dette publique de la Grèce. Cette dette pèse sur l'économie du pays de deux manières : par les craintes qu'elle fait naître chez les investisseurs sur la capacité de la Grèce à rembourser sa dette publique et par le poids du pai...

خيتي السادس

خيتي السادس معلومات شخصية تاريخ الميلاد القرن 21 ق.م تاريخ الوفاة القرن 21 ق.م عائلة الأسرة المصرية العاشرة الحياة العملية المهنة رجل دولة تعديل مصدري - تعديل خيتي السادس (نب كاو رع خيتي)Nebkaure Khetyثقالة من حجر اليشب عليها خرطوش بإسم نب كاو رع خيتي.فرعون مصرس�...

بروشنيف-أوسادا

بروشنيف-أوسادا (بالأوكرانية: Брошнів-Осада)‏ بروشنيف-أوسادا تاريخ التأسيس 1890 تقسيم إداري البلد أوكرانيا الإمبراطورية النمساوية المجرية [1] خصائص جغرافية إحداثيات 48°59′58″N 24°10′53″E / 48.999444444444°N 24.181388888889°E / 48.999444444444; 24.181388888889 المساحة 5.04 كيل�...

إفريقيا جنوب الصحراء

إفريقيا جنوب الصحراءمعلومات عامةجزء من إفريقياكيان إقليمي القارة إفريقيا المنطقة الزمنية توقيت وسط إفريقياتوقيت غرب أفريقياتوقيت شرق إفريقيا الإحداثيات 10°S 23°E / 10°S 23°E / -10; 23 يشترك في الحدود مع شمال إفريقيا عدد الأطفال خارج المدارس 97٬894٬515[1] (2015) لديه جزء �...

Herbert C. Brown

American chemist (1912–2004) For the Australian public servant, see Herbert Charles Brown (public servant). Herbert C. BrownBornHerbert BrovarnikMay 22, 1912London, England, UKDiedDecember 19, 2004(2004-12-19) (aged 92)Lafayette, Indiana, USNationalityAmericanAlma materUniversity of ChicagoKnown forOrganoboranesSpouse(s)Sarah Baylen (1937–2005; his death; 1 child)AwardsCentenary Prize (1955)William H. Nichols Medal (1959)National Medal of Science (1969) Elliott Cresson Meda...

Facing Worlds

Video game map in the Unreal Tournament series Facing WorldsUnreal Tournament locationFacing Worlds in Unreal Tournament (1999).First appearanceUnreal TournamentCreated byCedric FiorentinoGenreFirst-person shooter Facing Worlds, also known by its filename CTF-Face, is a multiplayer map for the first-person shooter video games Unreal Tournament (1999), Unreal Tournament 2003, Unreal Tournament 2004, Unreal Tournament 3, and Unreal Tournament (2014). Consisting of two identical towers separated...

烏茲別克國家奧林匹克委員會

烏茲別克國家奧林匹克委員會成立時間1992年總部烏茲別克塔什干主席Umid Akhmatdjanov網站http://olympic.uz/奥林匹克委员会信息國家或地區乌兹别克斯坦IOC編碼UZB加入IOC1993年区域组织亞洲奧林匹克理事會烏茲別克國家奧林匹克委員會（烏茲別克語：Oʻzbekiston Milliy Olimpiya qoʻmitasi；英語：National Olympic Committee of the Republic of Uzbekistan）是烏茲別克的國家奧林匹克委員會。該組織成�...

Maya religion

Beliefs of the ancient Maya people This article is about the traditional religion of the Maya peoples. For the meaning of Maya in the religious traditions of India, see Maya (religion). Maya mythologyand religionMaize god and Itzamna Practices Bloodletting Death rituals Dedication rituals Pilgrimage Priesthood Sacrifice (Humans) Places Cave sites Middleworld Xibalba Deities and beings Death gods Jaguar gods Mams Acat Ah Peku Ah-Muzen-Cab Awilix Bacab Cabaguil Camazotz Chaac Chin Cizin Chiraka...

Fraudulent trading

Doing business with intent to defraud creditors Insolvency Processes Administration Bankruptcy Chapter 7 (US) CVA Conservatorship Dissolution Examinership IVA Liquidation Provisional liquidation Receivership Officials Insolvency practitioner Tribunal Regulatory agency Liquidator Referee in Bankruptcy Trustee in bankruptcy Claimants Creditor Preferential creditor Secured creditor Unsecured creditor Restructuring Administration (UK) Chapter 11 (US) Cram down Restructuring Scheme of arrangement ...

أميليا (فيلم)

لمعانٍ أخرى، طالع أميليا (توضيح). أميلياAmelia (بالإنجليزية) معلومات عامةالصنف الفني دراما، ملحميالمواضيع طيران — أميليا إيرهارت تاريخ الصدور 2009مدة العرض 111 دقيقةاللغة الأصلية الإنجليزيةالبلد كندا والولايات المتحدةمواقع التصوير هاميلتون — كولونيا — نوفا سكوشا موقع...