Gramática irrestrita

Em Teoria da computação, a Gramática irrestrita (conhecida também como Gramática com estrutura de frase) é também conhecida como Tipo 0 da Hierarquia de Chomsky, que são aquelas às quais nenhuma limitação é imposta. São capazes de gerar linguagens recursivamente enumeráveis. O universo das linguagens que se podem definir através dos mecanismos gerativos definidos pela gramática corresponde exatamente ao conjunto das linguagens que esta classe de gramática é capaz de gerar.

Definição formal

Uma gramática irrestrita é uma gramática formal , onde é um conjunto de símbolos não-terminais, é um conjunto de símbolos terminais, contém as produções da forma onde e são cadeias de símbolos em e não é uma cadeia vazia. Além disso, é o símbolo inicial. Como o nome implica, não há restrições nos tipos de produções que gramáticas irrestritas podem ter.

Vale notar que e não são necessariamente disjuntos, uma vez que gramáticas irrestritas não fazem distinção entre símbolos terminais e não-terminais. Tal distinção existe apenas para indicar quando parar ao gerar sentenças da gramática.

Gramáticas irrestritas e máquinas de Turing

Pode ser mostrado que gramáticas irrestritas caracterizam as linguagens recursivamente enumeráveis. Isto é o mesmo que dizer que para toda gramática irrestrita , existe alguma máquina de Turing capaz de reconhecer e vice-versa. Dada uma gramática irrestrita, tal máquina de Turing é simples de construir como uma máquina de Turing não-determinística , de duas fitas. A primeira fita contém a entrada w a ser testada e a segunda fita é usada pela máquina para gerar sentenças de . é como segue:

  1. Comece na esquerda da segunda fita e repetidamente escolha entre mover para a direita ou selecionar a posição atual da fita.
  2. De modo não-determinístico, escolha uma produção das produções em .
  3. Se aparecer em alguma posição na segunda fita, substitua por neste ponto, possivelmente deslocando os símbolos da fita para a esquerda ou direita dependendo dos tamanhos relativos entre e , i.e., se for maior que , desloca os símbolos da fita para a esquerda.
  4. Compare a sentença resultante na fita 2 com a palavra da fita 1. Se forem iguais, aceite. Caso contrário, volte para o passo 1.

É fácil perceber que esta máquina de Turing irá gerar todas (e apenas) as sentenças de na segunda fita depois que o último passo for executado um número arbitrário de vezes. Assim a linguagem é recursivamente enumerável. A construção reversa também é possível. Dada uma máquina de Turing, é possível criar uma gramática irrestrita.

Propriedades computacionais

Como pode ser esperado da equivalência entre gramáticas irrestritas e máquinas de Turing, o problema uma cadeia w pertencer ou não à linguagem de uma gramática irrestrita é indecidível. É perfeitamente possível criar uma gramática irrestrita universal, capaz de aceitar qualquer linguagem de outra gramática irrestrita, dada a descrição da linguagem, assim como é possível criar uma máquina de Turing universal. Assim, seria teoricamente possível construir uma linguagem de programação baseada em gramáticas irrestritas (e.g. Thue).

Teoria da computação

Teoria de autômatos: linguagem formal e gramática formal
Hierarquia
Chomsky 		Gramática Linguagem Reconhecedor
Tipo-0 Irrestrita Recursivamente enumerável Máquina de Turing
-- -- Recursiva Máquina de Turing que sempre para
Tipo-1 Sensível ao contexto Sensível ao contexto Autômato linearmente limitado
Tipo-2 Livre de contexto Livre de contexto Autômato com pilha
Tipo-3 Regular Regular Autômato finito


Ver também

Read other articles:

Kenyu Sugimoto

Kenyu Sugimoto 2013Informasi pribadiNama lengkap Kenyu SugimotoTanggal lahir 18 November 1992 (umur 31)Tempat lahir Prefektur Osaka, JepangPosisi bermain PenyerangKarier senior*Tahun Tim Tampil (Gol)2010-2014 Cerezo Osaka 2012 →Tokyo Verdy 2015 Kawasaki Frontale 2016- Cerezo Osaka * Penampilan dan gol di klub senior hanya dihitung dari liga domestik Kenyu Sugimoto (lahir 18 November 1992) adalah pemain sepak bola asal Jepang. Karier Kenyu Sugimoto pernah bermain untuk Cerezo Osaka, To...

 

العلاقات الزيمبابوية الساموية

العلاقات الزيمبابوية الساموية زيمبابوي ساموا   زيمبابوي   ساموا تعديل مصدري - تعديل   العلاقات الزيمبابوية الساموية هي العلاقات الثنائية التي تجمع بين زيمبابوي وساموا.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدولتين: وجه الم...

 

Alfonso, Cavite

Municipality in Cavite, Philippines 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: Alfonso, Cavite – news · newspapers · books · scholar · JSTOR (January 2016) (Learn how and when to remove this template message) Municipality in Calabarzon, PhilippinesAlfonsoMunicipalityMunicipality of AlfonsoDowntown area ...

Criminal Minds: Suspect Behavior

2011 American television series Criminal Minds: Suspect BehaviorGenre Police procedural Drama Thriller Created by Edward Allen Bernero Chris Mundy Starring Forest Whitaker Janeane Garofalo Michael Kelly Beau Garrett Matt Ryan Kirsten Vangsness Country of originUnited StatesOriginal languageEnglishNo. of seasons1No. of episodes13ProductionExecutive producers Chris Mundy Edward Allen Bernero Mark Gordon Deborah Spera Running time45 minutesProduction companies The Mark Gordon Company Bernero Pro...

 

Begadang (film)

Untuk kegunaan lain, lihat Begadang (disambiguasi). BegadangSutradaraMaman FirmansjahProduserZainal AbidinDitulis olehMaman FirmansyahRhoma IramaPemeranRhoma IramaYati OctaviaBilly ArgoChitra DewiAde IrawanSukarno M. NoorA. Hamid AriefDoddy SukmaYetty LorenKomalasariFakhri AmrullahUrip ArphanPipiet SandraDistributorHanna Internasional FilmTanggal rilis1978Durasi111 menitNegaraIndonesia Begadang adalah film Indonesia yang dirilis pada tahun 1978 dengan disutradarai oleh Maman Firmansjah. Film ...

 

جان أسعد حداد

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (فبراير 2021) جان أسعد حداد معلومات شخصية الميلاد 17 ديسمبر 1926   لبنان  تاريخ الوفاة 22 يناير 2021 (94 سنة)   مواطنة لبنان  مناصب مطران كاثوليكي   في المنصب26 أكتوبر 19...

Ramat HaSharon

Questa voce sull'argomento centri abitati di Israele è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Ramat HaSharonautorità locale(HE) רמת השרון Ramat HaSharon – VedutaVeduta di Palm Avenue LocalizzazioneStato Israele DistrettoTel Aviv SottodistrettoNon presente AmministrazioneSindacoYitzhak Rochberger TerritorioCoordinate32°08.16′N 34°50.24′E / 32.136°N 34.837333°E32.136; 34.837333 (Ramat HaSharon)Coordinate...

 

Brothers to the Rescue

Anti-Cuba organization run by Cuban exiles in Florida Brothers to the RescueHermanos al RescatePurposeAid balseros and dissidents in CubaLocationMiami, United StatesMethods Rescue rafters spotted in the Florida straits by aircraft Airdropping dissident leaflets over Cuba Websitehermanos.org Brothers to the Rescue (Spanish: Hermanos al Rescate) is a Miami-based activist nonprofit organization headed by José Basulto. Formed by Cuban exiles, the group is widely known for its opposition to the C...

 

Mad Mad House

American TV series or program Mad Mad HouseTitle cardCreated byArthur SmithKent WeedStarringFiona HorneDavid Avocado WolfeArt AguirreDon HenrieTa'Shia AsantiCountry of originUnited StatesNo. of seasons1No. of episodes10ProductionRunning time60 minutesOriginal releaseNetworkSyFyReleaseMarch 4 (2004-03-04) –April 29, 2004 (2004-04-29) Mad Mad House is a 2004 reality television series about a group of ten contestants competing for $100,000. The contestants live together in a ho...

Зевник (рыбалка)

Зевник и рыбацкие щипцы Зе́вник — рыболовная принадлежность в виде одно-двух винтовой пружины с удлинёнными концами. Предназначен для извлечения крючка или блесны из пасти хищной рыбы (такой как щука, таймень или судак). Во время рыбной ловли случается, что рыба глубо�...

 

哈萨克斯坦总统

此条目序言章节没有充分总结全文内容要点。 (2019年3月21日)请考虑扩充序言，清晰概述条目所有重點。请在条目的讨论页讨论此问题。 哈萨克斯坦總統哈薩克總統旗現任Қасым-Жомарт Кемелұлы Тоқаев卡瑟姆若马尔特·托卡耶夫自2019年3月20日在任任期7年首任努尔苏丹·纳扎尔巴耶夫设立1990年4月24日（哈薩克蘇維埃社會主義共和國總統） 哈萨克斯坦 哈萨克斯坦政府...

 

Be with You (Atomic Kitten song)

2002 single by Atomic Kitten Be with YouSingle by Atomic Kittenfrom the album Feels So Good (Special Edition) and Ladies Night A-sideThe Last GoodbyeReleased25 November 2002 (2002-11-25)StudioMetropolis (London, England)GenreDance-popdiscoLength3:38LabelInnocentVirginSongwriter(s)Greg WilsonTracey CarmenMartin FosterJeff LynneProducer(s)Ash HowesMartin HarringtonAtomic Kitten singles chronology The Tide Is High (Get the Feeling) (2002) The Last Goodbye / Be with You (2002) Love...

Pottier P.70

P.70 Pottier P.170S Role Sport aircraftType of aircraft National origin France Manufacturer Homebuilt Designer Jean Pottier First flight 1970s The Pottier P.70 was a single-seat, single-engine sport aircraft developed in France in the 1970s and marketed for homebuilding.[1] It was a mid-wing cantilever monoplane of conventional design with an enclosed cockpit.[2] Originally designed with fixed, tricycle undercarriage, the plans were later revised to offer a fixed, tailwheel o...

 

Nisbah minyak dan gas bumi

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 Desember 2022. Nisbah gas dan minyak bumi (bahasa Inggris: gas oil ratio, disingkat GOR) adalah taksiran perbandingan antara jumlah gas dan minyak dalam suatu reservoar, diukur dalam satuan takaran baku, misalnya m3/m3, ft3/bbl. Angka nisbah gas dan minyak bumi ini ...

 

Liz Claiborne

American fashion designer (1929–2007) For the company once named after the designer, see Kate Spade & Company. Liz ClaiborneClaiborne in 1982BornAnne Elisabeth Jane Claiborne(1929-03-31)March 31, 1929[citation needed]Brussels, BelgiumDiedJune 26, 2007(2007-06-26) (aged 78)New York City, U.S.NationalityAmericanEducationFine Arts School and Painters Studio, Belgium (1947)Nice Academy (1948)LabelLiz ClaiborneSpousesBen Shultz (m. 1950; div. 1954)Arthur Ortenberg (m. 1957)Relat...

Aïr Mountains

Mountain range in northern Niger Aïr redirects here. For the state of Aïr which formerly governed this region, see Sultanate of Agadez. For other uses, see Mount Ayr (disambiguation). Aïr MountainsAïr Massif, AyrThe Timia Valley, in the Aïr MountainsHighest pointPeakMont Idoukal-n-TaghèsElevation2,022 m (6,634 ft)DimensionsArea84,000 km2 (32,000 sq mi)NamingNative nameAyar (Tamashek)Azbin (Hausa) (eastern)Abzin (Hausa) (western)Geogra...

 

Вооружённые силы Дании

Вооружённые силы Даниидат. Danske Forsvaret Эмблема вооружённых сил Дании Страна Дания Подчинение Министерство обороны Дании Тип вооружённые силы Включает в себя Сухопутные войска ДанииВоенно-морские силы ДанииВоенно-воздушные силы ДанииDefence Command[вд] Участие в Кальмарская во�...

 

Литовское национальное движение

Лито́вское национа́льное движе́ние (лит. Lietuvių tautinis sąjūdis, традиционно известное в историографии как Лит́овское национа́льное пробужде́ние лит. Lietuvių tautinis atgimimas) — борьба литовцев за право на своё национальное самоопределение. Связано с тем, что в XVIII веке Литва вошла в...

Elliott Sadler

American racing driver (born 1975) NASCAR driver Elliott SadlerSadler at Road America in 2018BornElliott William Barnes Sadler (1975-04-30) April 30, 1975 (age 49)Emporia, Virginia, U.S.Height6 ft 2 in (1.88 m)Weight195 lb (88 kg)Achievements1983–1984 Virginia State Karting ChampionshipNorth Carolina Gold Cup 1991–19921995 South Boston Speedway track champion2017 NASCAR Xfinity Series regular season champion 2004, 2006 Gatorade Duel WinnerAwards2011 NASCAR Na...

 

Graffignano

Graffignanocomune Graffignano – Veduta LocalizzazioneStato Italia Regione Lazio Provincia Viterbo AmministrazioneSindacoRossi Piero (lista civica #oltre) dal 27-5-2019 TerritorioCoordinate42°34′24″N 12°12′09″E42°34′24″N, 12°12′09″E (Graffignano) Altitudine187 m s.l.m. Superficie29,1 km² Abitanti2 093[1] (31-8-2022) Densità71,92 ab./km² FrazioniSipicciano Comuni confinantiAlviano (TR), Attigliano (TR), Bomarzo, Civ...