Lenguaje recursivamente enumerable

En matemáticas, lógica e informática, un lenguaje recursivamente enumerable es un tipo de lenguaje formal que es también llamado parcialmente decidible o Turing-computable. Son conocidos como lenguajes tipo-0 en la Jerarquía de Chomsky.

Definición

Aunque existen varias definiciones equivalentes, ésta es una de las principales:

  1. Un lenguaje recursivamente enumerable es un lenguaje formal para el cual existe una máquina de Turing que acepta y se detiene con cualquier cadena del lenguaje. Pero que puede parar y rechazar, o bien iterar indefinidamente, con una cadena que no pertenece al lenguaje, en contraposición a los lenguajes recursivos en cuyo caso se requiere que la máquina de Turing pare en todos los casos.

Todos los lenguajes regulares, independientes de contexto, dependientes de contexto y recursivos son recursivamente enumerables.

Propiedades de cierre

Los lenguajes recursivamente enumerables son cerrados con las siguientes operaciones. Esto es, si y son dos lenguajes recursivamente enumerables, entonces los siguiente lenguajes son recursivamente enumerables también:

  • el cierre estrella de
  • la concatenación de y
  • la unión de y
  • la intersección de y

Nótese que los lenguajes recursivamente enumerables no son cerrados con la diferencia ni el complementario.

  • puede no ser recursivamente enumerable
  • es recursivamente enumerable si y solo si es también recursivo.

Véase también

Read other articles:

Daftar nominasi dan pemenang Indonesian Choice Awards

Indonesian Choice Awards adalah sebuah ajang penghargaan yang digelar oleh NET. yang dimulai pada tahun 2014 saat NET. berulang tahun yang pertama. Pemenang Indonesian Choice Awards dipilih langsung oleh publik melalui Facebook dan Twitter.[1] Berikut ini daftar nominasi dan pemenang Indonesian Choice Awards berdasarkan kategori penghargaan. Kategori yang dihadirkan 2014 2015 2016 2017 2018 Song of the Year Ya Ya Ya Ya Ya Album of the Year Ya Ya Ya Ya Ya Male Singer of the Year Ya Ya ...

 

East Village, San Diego

For other uses, see East Village (disambiguation). Neighborhood of San Diego in San Diego, CaliforniaEast Village, San DiegoNeighborhood of San DiegoEast VillageEast Village, San DiegoLocation within Central San DiegoCoordinates: 32°43′27″N 117°10′2″W / 32.72417°N 117.16722°W / 32.72417; -117.16722Country United States of AmericaState CaliforniaCounty San DiegoCity San DiegoZIP Code92101Area code619Websiteeastvillagesandiego.com Modern studio apar...

 

1988 United States presidential election in Arizona

Main article: 1988 United States presidential election 1988 United States presidential election in Arizona ← 1984 November 8, 1988 1992 →   Nominee George H. W. Bush Michael Dukakis Party Republican Democratic Home state Texas Massachusetts Running mate Dan Quayle Lloyd Bentsen Electoral vote 7 0 Popular vote 702,541 454,029 Percentage 59.95% 38.74% County Results Bush   40–50%   50–60%   60–70% Dukakis  ...

List of Recorded Texas Historic Landmarks (Anderson-Callahan)

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: List of Recorded Texas Historic Landmarks Anderson-Callahan – news · newspapers · books · scholar · JSTOR (April 2017) (Learn how and when to remove this template message) The following is an introductory partial list in a series of Recorded Texas Histori...

 

Mercedes-Benz Kelas-C

Mercedes-Benz Kelas-CInformasiProdusenMercedes-BenzMasa produksi1993-sekarangBodi & rangkaKelasMobil eksekutif kompakKronologiPendahuluMercedes-Benz 190 E (W201) Mercedes-Benz Kelas-C merupakan sebuah mobil eksekutif kompak yang diciptakan produsen otomotif Jerman, Mercedes-Benz, sejak tahun 1993. Di Indonesia, mobil ini dijual dalam beberapa varian seperti C200, C250, dan C300. Mobil ini merupakan penerus dari Mercedes-Benz W201. W201 (1982-1993) Artikel utama: Mercedes-Benz W201 Mercede...

 

Felixstowe F.5

Felixstowe F.5 Felixstowe F.5s in formation, 1928.[1] Role Military flying boatType of aircraft National origin United Kingdom Manufacturer Seaplane Experimental Station (1)Short Brothers (23)Dick, Kerr & Co. (2)Phoenix Dynamo Manufacturing Company (17)Gosport Aircraft Company (10) S.E. Saunders LtdBoulton Paul Ltd (hulls only)Aircraft Manufacturing Co. LtdYokosuka Naval Air Technical Arsenal (10)Hiro Naval Arsenal (60) Aichi (40) Designer John Cyril Porte First flight November 1...

Bawang goreng

Indonesian crispy fried shallot Bawang gorengIndonesian crispy bawang goreng or fried shallotTypefried onionPlace of originIndonesiaMain ingredientsshallots  Media: Bawang goreng Bawang goreng is an Indonesian crispy fried shallot condiment, commonly deep-fried, and a popular garnish to be sprinkled upon various dishes of Indonesian cuisine.[1] It is quite similar to a crisp fried onion.[2] Ingredients Compared to onions, shallots are much smaller in size and more int...

 

1980 United States elections

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: 1980 United States elections – news · newspapers · books · scholar · JSTOR (March 2015) (Learn how and when to remove this message) 1980 United States elections← 1978          1979       &...

 

Roma (mitologi)

Penggambaran Roma di dalam koin denarius dari tahun 93-92 SM. Dalam agama Romawi Kuno, Roma adalah seorang dewi yang melambangkan kota Roma dan juga negara Romawi. Pada masa Kekaisaran Romawi, kultus dewi Roma pertama-tama muncul di wilayah timur karena lebih mudah melebur dengan tradisi Helenistik. Kultus ini menyanjung kekuatan Romawi dan membuat setia warga setempat. Kultus dewi Roma lalu menjadi bagian dari kultus kekaisaran, dan Kaisar Augustus sendiri menyetujui pembangunan kuil-kuil ya...

ソー (オー＝ド＝セーヌ県)

Sceaux 行政国 フランス地域圏 (Région) イル＝ド＝フランス地域圏県 (département) オー＝ド＝セーヌ県郡 (arrondissement) アントニー郡小郡 (canton) 小郡庁所在地INSEEコード 92071郵便番号 92330市長（任期） フィリップ・ローラン（2008年-2014年）自治体間連合 (fr) メトロポール・デュ・グラン・パリ人口動態人口 19,679人（2007年）人口密度 5466人/km2住民の呼称 Scéens地理座標 北緯48度4...

 

WTWF

Radio station in Fairview, Pennsylvania WTWFFairview, PennsylvaniaBroadcast areaErie, PennsylvaniaFrequency93.9 MHzBranding93.9 The WolfProgrammingFormatCountryAffiliationsPremiere NetworksOwnershipOwneriHeartMedia, Inc.(iHM Licenses, LLC)Sister stationsWFNN, WJET, WRKT, WEBG, WRTS, WXBBHistoryFirst air dateOctober 2001; 22 years ago (2001-10)Former call signsWRPL (2001–2003)WUSE (2003–2006)Call sign meaningW The WolFTechnical informationFacility ID76244ClassAERP6,0...

 

Goddess in the Doorway

2001 studio album by Mick JaggerGoddess in the DoorwayStudio album by Mick JaggerReleased19 November 2001RecordedFebruary and May 2000, January–February and April–June 2001StudioRoxie (Miami)Third Stone (Los Angeles)Drive By (Los Angeles)Rumbo (Los Angeles)Chiswick (London)Metropolis (London)Norfolk Lodge (Richmond)Mick Jagger's hotel room (Heidkamp)Hit Factory (New York City)GenreRockLength56:51LabelVirginProducerMatt Clifford, Marti Frederiksen, and Mick Jagger with Jerry 'Wond...

Member state of the European Union

State that is a participant in the treaties of the European Union (EU) Member state of the European UnionMap (clickable)CategoryMember stateLocationEuropean UnionCreated1952/1958/1993[note 1]Number27 (as of 2023)Possible typesRepublics (21)Monarchies (6)Populations 447,206,135 (2020)[1]Areas4,233,255 km2 (1,634,469 sq mi)GovernmentParliamentary representative democracy (21)Semi-presidential representative democracy (5)Presidential representative democracy (1) Th...

 

Corn Laws

19th-century trade restrictions on import food and grain in Great Britain For the British-Canadian trading act, see Canada Corn Act. The 1815 Corn Law, officially An Act to amend the Laws now in force for regulating the Importation of Corn The Corn Laws were tariffs and other trade restrictions on imported food and corn enforced in the United Kingdom between 1815 and 1846. The word corn in British English denoted all cereal grains, including wheat, oats and barley.[1] The laws were de...

 

Media Research Center

Conservative media watchdog group based in Virginia Media Research CenterFoundedOctober 1, 1987FounderL. Brent Bozell IIIType501(c)(3) nonprofit[1]FocusAllegations of liberal media biasLocationHerndon, Virginia, U.S.MethodEditorials, online newsletters, reports, conservative activism, right-wing activismKey peopleTim Graham, Rich Noyes, Brent Baker, Dan SchneiderWebsitemrc.org This article is part of a series onConservatismin the United States Schools Compassionate Fiscal Fusion Liber...

Jet Pilot (film)

1957 film by Josef von Sternberg Jet PilotTheatrical release posterDirected byJosef von SternbergWritten byJules FurthmanProduced byJules FurthmanHoward Hughes (presenter)StarringJohn WayneJanet LeighCinematographyWinton C. HochEdited byJim Wilkinson (Ed supv)Michael R. McAdamHarry MarkerWilliam M. MooreMusic byBronislau KaperProductioncompanyRKO Radio PicturesDistributed byUniversal-InternationalRelease dates September 25, 1957 (1957-09-25) (Premiere-Los Angeles) October&#...

 

Aubrey (song)

1973 single by BreadAubreyDutch single releaseSingle by Breadfrom the album Guitar Man B-sideDidn't Even Know Her NameReleased1973Recorded1972GenreSoft rockLength3:39LabelElektraSongwriter(s)David GatesProducer(s)David GatesBread singles chronology Sweet Surrender (1972) Aubrey (1973) Lost Without Your Love (1976) Aubrey is a song written and composed by American singer-songwriter David Gates, and originally recorded by the soft rock group Bread, of which Gates was the leader and primary musi...

 

Rekha

Indian actress (born 1954) For the South Indian actress, see Rekha (South Indian actress). For other uses, see Rekha (disambiguation). RekhaRekha in 2011BornBhanurekha Ganesan (1954-10-10) 10 October 1954 (age 69)Madras, Madras State, IndiaOther namesRekha Agarwal[1]OccupationActressYears active1958–presentWorksFull listSpouse Mukesh Agarwal ​ ​(m. 1990; died 1990)​ParentsGemini Ganesan (father)Pushpavalli (mother)Relati...

Hugh Mackail

Scottish Presbyterian minister (1640–1666) Hugh MackailMackail's executionPersonal detailsBornvarious spellings: Hugh or Hew Mackail, McKail, M'Kail, M'Kell, McKel, MacKell, M'Kaill, Mackailec1640Died1666market-cross EdinburghDenominationChurch of Scotland Hugh Mackail (various spellings) (c. 1640–1666), Scottish martyr, was born about 1640 at Liberton, near Edinburgh. His father was Matthew Mackail who was minister at Bothwell before being deprived of his ministry by the government in 1...

 

Carolinas

Halaman ini berisi artikel tentang wilayah geografis di Amerika Serikat tenggara. Untuk kepulauan di Samudra Pasifik yang sebelumnya dikenal sebagai Carolinas, lihat Kepulauan Caroline. CarolinasWilayahKoordinat: 34°48′17″N 79°40′31″W / 34.80472°N 79.67528°W / 34.80472; -79.67528NegaraAmerika SerikatKedua negara bagian Carolina Utara Carolina SelatanKota besarAsheville, N.C.Charleston, S.C.Charlotte, N.C.Columbia, S.C.Greensboro, N.C.Greenville, S...