Omega-regular language

The ω-regular languages are a class of ω-languages that generalize the definition of regular languages to infinite words.


Formal definition

An ω-language L is ω-regular if it has the form

  • Aω where A is a regular language not containing the empty string
  • AB, the concatenation of a regular language A and an ω-regular language B (Note that BA is not well-defined)
  • A ∪ B where A and B are ω-regular languages (this rule can only be applied finitely many times)

The elements of Aω are obtained by concatenating words from A infinitely many times. Note that if A is regular, Aω is not necessarily ω-regular, since A could be for example {ε}, the set containing only the empty string, in which case Aω=A, which is not an ω-language and therefore not an ω-regular language.

It is a straightforward consequence of the definition that the ω-regular languages are precisely the ω-languages of the form A1B1ω ∪ ... ∪ AnBnω for some n, where the Ais and Bis are regular languages and the Bis do not contain the empty string.

Equivalence to Büchi automaton

Theorem: An ω-language is recognized by a Büchi automaton if and only if it is an ω-regular language.

Proof: Every ω-regular language is recognized by a nondeterministic Büchi automaton; the translation is constructive. Using the closure properties of Büchi automata and structural induction over the definition of ω-regular language, it can be easily shown that a Büchi automaton can be constructed for any given ω-regular language.

Conversely, for a given Büchi automaton A = (Q, Σ, δ, I, F), we construct an ω-regular language and then we will show that this language is recognized by A. For an ω-word w = a1a2... let w(i,j) be the finite segment ai+1...aj-1aj of w. For every q, q' ∈ Q, we define a regular language Lq,q' that is accepted by the finite automaton (Q, Σ, δ, q, {q'}).

Lemma: We claim that the Büchi automaton A recognizes the language ⋃q∈I,q'∈F Lq,q' (Lq',q' − {ε} )ω.
Proof: Let's suppose word w ∈ L(A) and q0,q1,q2,... is an accepting run of A on w. Therefore, q0 is in I and there must be a state q' in F such that q' occurs infinitely often in the accepting run. Let's pick the strictly increasing infinite sequence of indexes i0,i1,i2... such that, for all k≥0, qik is q'. Therefore, w(0,i0)∈Lq0,q' and, for all k≥0, w(ik,ik+1)∈Lq',q' . Therefore, w ∈ Lq0,q' (Lq',q' )ω.
Conversely, suppose w ∈ Lq,q' (Lq',q' − {ε} )ω for some q∈I and q'∈F. Therefore, there is an infinite and strictly increasing sequence i0,i1,i2... such that w(0,i0) ∈ Lq,q' and, for all k≥0, w(ik,ik+1)∈Lq',q' . By definition of Lq,q', there is a finite run of A from q to q' on word w(0,i0). For all k≥0, there is a finite run of A from q' to q' on word w(ik,ik+1). By this construction, there is a run of A, which starts from q and in which q' occurs infinitely often. Hence, w ∈ L(A).

Equivalence to Monadic second-order logic

Büchi showed in 1962 that ω-regular languages are precisely the ones definable in a particular monadic second-order logic called S1S.

Bibliography

  • Wolfgang Thomas, "Automata on infinite objects." In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B: Formal Models and Semantics, pages 133-192. Elsevier Science Publishers, Amsterdam, 1990.

Read other articles:

Grigory Kiriyenko

Grigory KiriyenkoInformasi pribadiLahir29 September 1965 (umur 58)Moskwa, SFSR Rusia, Uni Soviet OlahragaOlahragaAnggar Rekam medali Anggar putra Olimpiade Mewakili  Tim Gabungan 1992 Barcelona Tim sabel Mewakili  Rusia 1996 Atlanta Tim sabel Grigory Anatolyevich Kiriyenko (Rusia: Григорий Анатольевич Кириенкоcode: ru is deprecated ) (lahir 29 September 1965 di Novosibirsk) adalah seorang atlet anggar asal Rusia. Ia memenangkan dua medali Oimpiade ema...

 

Национальное географическое общество

У этого термина существуют и другие значения, см. National Geographic. Национальное географическое обществоNational Geographic Society Административный центр Вашингтон, США[1][2][…] Локация  США[3] Тип организации научная ассоциация[d], кинокомпания[d] и издательство Осно...

 

Joni Ernst

Joni Ernst Joni Kay Ernst (née Culver; lahir 1 Juli 1970)[1] adalah seorang politikus dan veteran asal Amerika Serikat yang menjabat sebagai Senator Amerika Serikat junior untuk Iowa sejak 2015.[2] Sebagai anggota Partai Republik, ia menjabat dalam Senat Negara Bagian Iowa dari 2011 sampai 2014. Ernst bertugas dalam Garda Nasional Angkatan Darat Iowa dari 1993 sampai 2015, purnt tugas sebagai letnan kolonel.[3] Referensi ^ Ernst, Gail. Joni Kay Ernst – Plaza of Hero...

Sony BMG

Artikel ini membutuhkan rujukan tambahan agar kualitasnya dapat dipastikan. Mohon bantu kami mengembangkan artikel ini dengan cara menambahkan rujukan ke sumber tepercaya. Pernyataan tak bersumber bisa saja dipertentangkan dan dihapus.Cari sumber: Sony BMG – berita · surat kabar · buku · cendekiawan · JSTOR (Januari 2023) Sony BMG Music EntertainmentIndustriMusik dan HiburanNasibPembagian dari Bertelsmann dibeli oleh SonyPenerusSony MusicBMG Rights Man...

 

James Ruse Drive

Road in Sydney, Australia James Ruse DriveNew South WalesJames Ruse Drive Bridge over the Parramatta RiverSoutheast endNorthwest endCoordinates 33°50′00″S 151°01′07″E / 33.833404°S 151.018685°E / -33.833404; 151.018685 (Southeast end) 33°47′30″S 150°59′53″E / 33.791587°S 150.997919°E / -33.791587; 150.997919 (Northwest end) General informationTypeHighwayLength6.4 km (4.0 mi)[1]OpenedJune 1977 (Fi...

 

The Treasure of the City of Ladies

Manual of education by medieval Italian-French author Christine de Pizan Christine de Pizan presenting The Treasure to Margaret of Burgundy The Treasure of the City of Ladies (Le trésor de la cité des dames, also known The Book of the Three Virtues) is a manual of education by medieval Italian-French author Christine de Pisan. Finished, like her previous The Book of the City of Ladies, by the year 1405, and dedicated to Margaret of Burgundy at a time when Christine was writing works for Mar...

Pemilihan umum Italia 2006

Artikel ini perlu diterjemahkan dari bahasa Inggris ke bahasa Indonesia. Artikel ini ditulis atau diterjemahkan secara buruk dari Wikipedia bahasa Inggris. Jika halaman ini ditujukan untuk komunitas bahasa Inggris, halaman itu harus dikontribusikan ke Wikipedia bahasa Inggris. Lihat daftar bahasa Wikipedia. Artikel yang tidak diterjemahkan dapat dihapus secara cepat sesuai kriteria A2. Jika Anda ingin memeriksa artikel ini, Anda boleh menggunakan mesin penerjemah. Namun ingat, mohon tidak men...

 

Пугачёва, Алла Борисовна

Запрос «Пугачёва» перенаправляется сюда; см. также другие значения. Алла Пугачёва На фестивале «Славянский базар в Витебске», 2016 год Основная информация Полное имя Алла Борисовна Пугачёва Дата рождения 15 апреля 1949(1949-04-15) (75 лет) Место рождения Москва, СССР[1]...

 

2008 Los Angeles Dodgers season

Major League Baseball team season 2008 Los Angeles DodgersNational League West ChampionsLeagueNational LeagueDivisionWestBallparkDodger StadiumCityLos AngelesRecord84–78 (.519)Divisional place1stOwnersFrank McCourtPresidentJamie McCourtGeneral managersNed CollettiManagersJoe TorreTelevisionFSN Prime TicketKCAL (9) Vin Scully, Charley Steiner, Steve LyonsRadioKABC Vin Scully, Rick Monday, Charley Steiner KHJ Jaime Jarrín, Pepe Yñiguez, Fernando Valenzuela ← 2007 Seasons 20...

United Aircraft and Transport Corporation

Vertically-integrated, amalgamated U.S. aviation company United Aircraft and Transport CorporationCompany typeHolding companyIndustryAerospaceFoundedFebruary 1, 1929 (1929-02-01)FoundersWilliam E. BoeingFrederick RentschlerDefunctSeptember 26, 1934 (September 26, 1934)SuccessorBoeing Airplane CompanyUnited AircraftUnited AirlinesHeadquartersHartford, Connecticut, United States of America The United Aircraft and Transport Corporation was formed in 1929, when William Boeing ...

 

Leopoldo Metlicovitz

Italian painter Leopoldo Metlicovitz (17 July 1868 – 19 October 1944) was an Italian painter, illustrator and poster designer. Metlicovitz in 1900 Together with Leonetto Cappiello, Adolf Hohenstein, Giovanni Maria Mataloni and Marcello Dudovich, he is considered one of the fathers of modern Italian poster art. Biography Leopoldo Metlicovitz (right) with Giuseppe Verdi, Guiditta Ricordi and Giulio Ricordi. Villa Verdi, 1900. Son of a merchant of Dalmatian origins (the family name was origin...

 

Topsham railway station

Railway station in Devon, England TopshamGeneral informationLocationTopsham, ExeterEnglandCoordinates50°41′09″N 3°27′50″W / 50.68588°N 3.46401°W / 50.68588; -3.46401Grid referenceSX966883Managed byGreat Western RailwayPlatforms2Other informationStation codeTOPClassificationDfT category F2HistoryOriginal companyLondon and South Western RailwayPost-groupingSouthern RailwayKey datesOpened1861Passengers2018/19 0.239 million2019/20 0.229 million2020/21 67,918202...

ATP Bordeaux 1987

ATP Bordeaux 1987 Sport Tennis Data 13 luglio - 19 luglio Edizione 9a Superficie Terra rossa Campioni Singolare Emilio Sánchez Doppio Sergio Casal / Emilio Sánchez L'ATP Bordeaux 1987 è stato un torneo di tennis giocato sulla terra rossa. È stata la 9ª edizione dell'ATP Bordeaux, che fa parte del Nabisco Grand Prix 1987. Il torneo si è giocato a Bordeaux in Francia, dal 13 al 19 luglio 1987. Indice 1 Campioni 1.1 Singolare maschile 1.2 Doppio maschile 2 Collegamenti esterni Campioni Si...

 

List of Ancestral Puebloan dwellings in Utah

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 Ancestral Puebloan dwellings in Utah – news · newspapers · books · scholar · JSTOR (July 2011) (Learn how and when to remove this message) Part of a series onAncestral Puebloan dwellings Arizona Chihuahua Colorado Nevada New Mexico Sonora Texas Utah vt...

 

Queen's Hall, Edinburgh

The Queen's HallFormer namesNewington & St Leonard's Parish Church (1932–1976)Newington Parish Church (1834–1932)Hope Park Chapel (1824–1834)General informationStatusActiveArchitectural styleNeoclassicalLocationEdinburgh, ScotlandAddress85-89 Clerk StreetEdinburghEH8 9JGCoordinates55°56′28.51″N 3°10′53.97″W / 55.9412528°N 3.1816583°W / 55.9412528; -3.1816583Named forElizabeth IIGroundbreaking1823Completed1824Renovated1978–1979Height35 metres (1...

Ilya Frank

Soviet physicist (1908–1990) For other uses, see Frank (disambiguation). In this name that follows Eastern Slavic naming customs, the patronymic is Mikhailovich and the family name is Frank. Ilya FrankИлья ФранкFrank in 1958BornIlya Mikhailovich Frank(1908-10-23)23 October 1908Saint Petersburg, Russian EmpireDied22 June 1990(1990-06-22) (aged 81)Moscow, Russian SFSR, Soviet UnionAlma materMoscow State UniversityKnown forCherenkov radiationTransition radiationFran...

 

مجلس السلام والأمن الإفريقي

مجلس السلام والأمن الإفريقي مجلس السلام والأمن الإفريقيالعلم الاتحاد الأفريقي النشيد: هيا نتحد ونتحتفل سوياً الأرض والسكان إحداثيات 9°00′00″N 38°44′29″E / 9.000044°N 38.741383°E / 9.000044; 38.741383   المساحة 29757900 كم² المركز الإداري  إثيوبيا، أديس أبابا جنوب إفريقيا، ميد�...

 

Hunting dog

Functional type of dog For other uses, see Hunting dog (disambiguation). Hunting dog A hunting dog is a canine that hunts with or for hunters. There are several different types of hunting dog developed for various tasks and purposes. The major categories of hunting dog include hounds, terriers, dachshunds, cur type dogs, and gun dogs. Further distinctions within these categories can be made, based upon the dog's skills and capabilities. They are usually larger and have a more sensitive smell ...

Yaneer Bar-Yam

American scientist and activist This article may have been created or edited in return for undisclosed payments, a violation of Wikipedia's terms of use. It may require cleanup to comply with Wikipedia's content policies, particularly neutral point of view. (January 2023) Yaneer Bar-YamBar-Yam (on the left) at Wikimania 2014Born1959 (age 64–65)Boston, MassachusettsEducationMassachusetts Institute of Technology (BS, PhD)Scientific careerFieldsComplex systems (Application to social, ...

 

Ed Groot

Dutch politician, journalist, columnist and civil servant (born 1957) Vincentius Aloysius (Ed) GrootMember of the House of RepresentativesIn office17 June 2010 – 23 March 2017 Personal detailsBorn (1957-12-26) 26 December 1957 (age 66)Grootebroek, Netherlands Vincentius Aloysius (Ed) Groot (born 26 December 1957 in Grootebroek) is a Dutch politician and former journalist, columnist and civil servant. As a member of the Labour Party (Partij van de Arbeid) he was an MP between 1...