زبان مستقل‌ازمتن قطعی

در نظریهٔ زبان صوری،زبان مستقل از متن قطعی (DCFL)، یک زیر مجموعهٔ سره از زبان‌های مستقل از متن می‌باشد. این زبانهای مستقل از متن هستند که می‌توانند بوسیلهٔ یک ماشین پشته‌ای قطعی پذیرفته شوند. DCFLها همیشه واضح هستند، به این معنی که آن‌ها یک گرامر واضح را می‌پذیرند، ولی هر. DCFL غیر تهی نیز یک گرامر مبهم را نیز می‌پذیرد. CFLهای واضح غیر قطعی نیز وجود دارند، بنابراین DCFLها یک زیر مجموعهٔ سره از CFLهای غیر مبهم را تشکیل می‌دهند. DCFLها علاقهٔ کاربردی زیادی دارند، آن طور که می‌توانند در زمان خطی تجزیه شوند و انواع محدود متنوع از DCFGها، تجزیه‌های کاربردی ساده‌ای را می‌پذیرند؛ بنابراین آن‌ها به‌طور گسترده‌ای در علوم کامپیوتر استفاده می‌شوند.

شرح

مفهوم DCFL بسیار مرتبط با ماشین پشته‌ای قطعی (DPDA). می‌باشد. این جایی است که اگر آن را قطعی کنیم، قدرت زبان یک ماشین پشته‌ای کاهش می‌یابد؛ ماشین پشته‌ای در انتخاب بین گزینه‌های حالت گذار مختلف ناتوان می‌شود و در نتیجه نمی‌تواند همهٔ زبان‌های مستقل از متن را تشخیص دهد. گرامرهای واضح همیشه یک DCFL را تولید نمی‌کنند. به‌طور مثال، زبان پالیندرام با طول زوج در الفبای ۰ و ۱ می‌باشد، گرامر مستقل از متن S → 0S0 | 1S1 | ε را دارد. یک رشتهٔ اختیاری از این زبان، نمی‌تواند بدون خواندن تمام این حروف در ابتدا تجزیه شود، به این معنا که یک ماشین پشته‌ای باید حالت‌های گذار مختلف را برای جا دادن طول‌های ممکن مختلف از رشته‌های با تجزیهٔ مشابه، امتحان کند.

ویژگی‌ها

زبان‌های مستقل از متن قطعی می‌توانند با ماشین‌های تورینگ قطعی در یک زمان چند جمله‌ای و فضای O(log2 n)، تشخیص داده شود. به عنوان نتیجه، DCFL زیر مجموعه‌ای از کلاس پیچیدگی SC می‌باشد. مجموعهٔ زبانه‌ای مستقل از متن قطعی، نسبت به اجتماع بسته نیست ولی نسبت به تفاضل بسته است.

اهمیت

زبان‌های این گروه اهمیت کاربردی زیادی در علوم کامپیوتر دارند، از آنجا که آن‌ها می‌توانند به‌طور کاراتری نسبت به زبان‌های مستقل از متن غیر قطعی تجزیه شوند. پیچیدگی برنامه و زمان اجرای ماشین پشته‌ای قطعی به‌طور گسترده‌ای کمتر از حالت غیر قطعی است. در راه‌اندازی ساده دومی باید در هر زمان که یک مرحلهٔ غیر قطعی رخ می‌دهد، کپی‌هایی از پشته‌ها بسازد. بهترین الگوریتم شناخته شده برای آزمون عضویت در هر زبان مستقل از متن، الگوریتم ولینت می‌باشد که (O(n2.378 زمان می‌گیرد، که n طول رشته است. از طرف دیگر، زبان‌های مستقل از متن قطعی می‌توانند در زمان (O(n بوسیلهٔ تجزیه کنندهٔ (LR(k پذیرفته شوند. این برای ترجمه زبان برنامه نویسی بسیار مهم است زیرا بسیاری از زبان‌های کامپیوتری به این گروه از زبان‌ها تعلق دارند.

منابع

https://en.wikipedia.org/wiki/Deterministic_context-free_language

Read other articles:

Man with a PlanGenreSitkomPembuat Jackie Filgo dan Jeff Filgo Pemeran Matt LeBlanc Liza Snyder Jessica Chaffin Matt Cook Grace Kaufman Hala Finley Matthew McCann Diana-Maria Riva Kevin Nealon Stacy Keach Kali Rocha Penata musikJohn KimbroughNegara asalAmerika SerikatBahasa asliInggrisJmlh. musim4Jmlh. episode69 (daftar episode)ProduksiProduser eksekutif Jackie Filgo Jeff Filgo Matt LeBlanc Michael Rotenberg Troy Zien Pengaturan kameraMulti-kameraDurasi22 menitRumah produksiDouble Double...

 

American college football season 2010 James Madison Dukes footballConferenceColonial Athletic AssociationRecord6–5 (3–5 CAA)Head coachMickey Matthews (12th season)Offensive coordinatorJeff DurdenDefensive coordinatorKyle GillenwaterHome stadiumBridgeforth Stadium(Capacity: 15,694)Seasons← 20092011 → 2010 Colonial Athletic Association football standings vte Conf Overall Team   W   L     W   L   No. 2 Delaware +^  ...

 

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Cet article ne cite pas suffisamment ses sources (mars 2012). Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références » En pratique : Quelles sources sont attendues ? Comme...

Bài viết này cần thêm chú thích nguồn gốc để kiểm chứng thông tin. Mời bạn giúp hoàn thiện bài viết này bằng cách bổ sung chú thích tới các nguồn đáng tin cậy. Các nội dung không có nguồn có thể bị nghi ngờ và xóa bỏ. Logo của Viện Viện Công nghệ Sinh học (tên tiếng Anh là Institute of Biotechnology (IBT)) là một viện nghiên cứu chủ đạo về các lĩnh vực Công nghệ Sinh học ở Việt Nam. Vi

 

Map of boundary as of 1971 Faringdon was a rural district in the administrative county of Berkshire from 1894 to 1974. It was formed under the Local Government Act 1894 based on that part of the Faringdon rural sanitary district which was in Berkshire; however, it also included for a time Lechlade, a small market town in Gloucestershire. It was situated in the northwest region of historic Berkshire, but the area was transferred to Oxfordshire in 1974 and is now in the southwestern region of t...

 

Komite untuk Lima Provinsi Utara Korea이북오도위원회 / 以北五道委員會 Bendera Lambang Peta Korea Utara dengan pembagian provinsi yang diklaim oleh Korea SelatanBahasa resmiKoreaPemerintahanBadan pemerintah di bawah Kementerian Keamanan dan Administrasi Publik• Gubernur Han Sang-sun (Provinsi Hwanghae)Baek Gu-Seop (Provinsi Pyeongan Utara)Baek Nam Jin (Provinsi Pyeongan Selatan)Park Ki-jeong (Provinsi Hamgyeong Utara)Hwang Deok-ho (Provinsi Hamgyeong Selatan) Pemerintah da...

This article reflects continually changing information from hundreds of sources. You can help by updating items to more recent figures from official sources. Cartogram of the world's population in 2018; each square represents 500,000 people. This is a list of countries and dependencies by population. It includes sovereign states, inhabited dependent territories and, in some cases, constituent countries of sovereign states, with inclusion within the list being primarily based on the ISO standa...

 

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: Tōkamachi – news · newspapers · books · scholar · JSTOR (March 2013) (Learn how and when to remove this template message) You can help expand this article with text translated from the corresponding article in Japanese. (February 2022) Click [show] for im...

 

Male Wijk van Brugge Locatie van de wijk Male Kerngegevens Gemeente Brugge Stadsdeel Sint-Kruis Coördinaten 51°12'36NB, 3°16'59OL Overig Postcode(s) 8310 Male is een oud gehucht in de Belgische provincie West-Vlaanderen en thans een wijk in de stad Brugge. Het ligt tussen Sijsele en Sint-Kruis (Brugge), op het grondgebied van Sint-Kruis, in de rand van de stedelijke agglomeratie van Brugge. Geschiedenis Male was in de middeleeuwen een heerlijkheid in het zuidoosten van Brugge. De naam kan ...

British attack on Dammam, 19th century Attack on DammamFort of DammamDate3-4 February 1866LocationDammamResult Saudi victoryBelligerents  United Kingdom Emirate of NejdCommanders and leaders Lieutenant Long Abdullah bin Faisal Al SaudStrength 1 ship UnknownCasualties and losses 3 killed5 wounded Unknown The Attack on Dammam was an 1866 military action by the British ship to destroy the fort in Dammam held by the Saudis; the attack, however, failed. Background In late 1865, the Saudis inv...

 

Photograph of the Sultan Achmad Nazaruddin (1858-81) taken during a Royal Netherlands Geographical Society expedition from 1877 - 1879, by Daniël David Veth. Part of a series on the History of Indonesia Timeline Prehistory Java Man 1,000,000 BP Flores Man 94,000–12,000 BP Toba catastrophe 75,000 BP Buni culture 400 BCE Hindu and Buddhist kingdoms Kutai Kingdom 350–1605 Tarumanagara Kingdom 400s–500s Kalingga Kingdom 500s–600s Melayu Kingdom 600s–1347 Srivijaya Empire 600s–1025 Sh...

 

American procedural drama television series Not to be confused with Lone Star (TV series). 9-1-1: Lone StarGenre Procedural drama Action Created by Ryan Murphy Brad Falchuk Tim Minear Starring Rob Lowe Liv Tyler Ronen Rubinstein Sierra McClain Jim Parrack Natacha Karam Brian Michael Smith Rafael L. Silva Julian Works Gina Torres Brianna Baker Kelsey Yates Skyler Yates Composers Mac Quayle Todd Haberman Justin Burnett Country of originUnited StatesOriginal languageEnglishNo. of seasons4No. of ...

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (مايو 2020) تحتاج هذه المقالة كاملةً أو أجزاءً منها إلى تدقيق لغوي أو نحوي. فضلًا ساهم في تحسينها من خلال الصيانة اللغوية والنحوية المناسبة. (يوليو 2020) تحوي هذه المقالة أو ...

 

Dutch politician Emre ÜnverÜnver in 2011Member of the House of RepresentativesIn office14 December 2016 – 15 February 2017Member of the municipal council of AmsterdamIn office11 March 2006 – 29 March 2018 Personal detailsBorn (1981-11-19) 19 November 1981 (age 42)Amsterdam, Netherlands[1]Political partyLabour Party Emre Ünver (born 19 November 1981) is a Dutch politician. He was a member of the House of Representatives for the Labour Party from 14 Decembe...

 

Historic site in New South Wales, AustraliaCronulla Post OfficeCronulla Post Office, 1926Location41 Cronulla Street, Cronulla, Sydney, New South Wales, AustraliaCoordinates34°03′10″S 151°09′08″E / 34.0529°S 151.1523°E / -34.0529; 151.1523Built1924ArchitectEdwin Hubert Henderson Commonwealth Heritage ListOfficial nameCronulla Post OfficeTypeListed place (Historic)Designated22 August 2012Reference no.106203 Location of Cronulla Post Office in Sydney Cron...

Croatian nobleman and general (1763–1817) This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help to improve this article by introducing more precise citations. (February 2021) (Learn how and when to remove this template message) Karl Paul von QuosdanovichBaron Karl Paul von QuosdanovichNative nameKarlo Pavao GvozdanovićBorn1763 (1763)Brezovac Žumberački, a village near Samobor, Kin...

 

1947 novel written by Thomas Mann This article is about the novel by Thomas Mann. For other uses, see Doctor Faustus. Doctor Faustus First edition cover (jacket) in EuropeAuthorThomas MannCountryGermanyLanguageGermanGenrePhilosophical novelPublication date1947Media typePrint Doctor Faustus is a German novel written by Thomas Mann, begun in 1943 and published in 1947 as Doktor Faustus: Das Leben des deutschen Tonsetzers Adrian Leverkühn, erzählt von einem Freunde (Doctor Faustus: The Li...

 

Women's shot put at the 2017 World Para Athletics Championship Events at the 2017 World Para Athletics ChampionshipsTrack events100 mmenwomen200 mmenwomen400 mmenwomen800 mmenwomen1500 mmenwomen5000 mmenwomen4×100 m relaymen4×400 m relaymenwomenField eventsLong jumpmenwomenTriple jumpmenHigh jumpmenShot putmenwomenDiscus throwmenwomenJavelin throwmenwomenClub throwmenwomenvte The women's shot put at the 2017 World Para Athletics Championships was held at the Olympic Stadium in London from 1...

Mia MayLahirHermine Pfleger(1884-06-02)2 Juni 1884Wina, Austria-HungariaMeninggal28 November 1980(1980-11-28) (umur 96)Los Angeles, California, Amerika SerikatPekerjaanPemeranTahun aktif1889–1924Suami/istriJoe May ​ ​(m. 1902; kematiannya 1954)​AnakEva MayTanda tangan Mia May (nama lahir Hermine Pfleger; 2 Juni 1884 – 28 November 1980) adalah seorang pemeran asal Austria.[1] Ia menikahi produser dan sutradara ...

 

Montenegrin politician Vladislav DajkovićВладислав ДајковићMember of the City Assembly of PodgoricaIncumbentAssumed office 12 April 2023 Personal detailsBorn (1992-01-13) 13 January 1992 (age 32)Cetinje, SFR Yugoslavia(now Montenegro)Political partyFree Montenegro(2021–present)Other politicalaffiliationsZBCG (in 2020)PCG (2018–2019)DEMOS (2015–2018)Alma materUniversity of BelgradeITES de MonterreyOccupationPolitical activist, politicianWebsitedajkovic.me Vladi...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!