Bunların nasıl isimlendirildikleri düzenli dillerdir

Question

Bu konuda yardıma ihtiyacım olan sorularım var. Düzenli diller olduklarını kanıtlamak zorundayım. DSQ ya da DF'nin 3. ve 4. soruda ne olduğu konusunda hiçbir fikrim yok. "Splus'a göre Teoriye Giriş" kitabım var ama DSQ ya da DF'den bahseden bir şey bulamadım.

1) L = {a .... a ∈ Σ *} Σ = {a, b}

2) Trancate (n) = {wa^nw ∈ Σ * bir ∈ Σ | a | = n}

3) DSQ = {a^s, b^s: s asal}

4) DF = {a^Nb^n: n> ya da buna eşit 0}

Answer 1

dört Bu diller düzenli değildir. Dillerin düzenli olmadığını kanıtlamak için kullanabileceğiniz birkaç farklı teknik vardır. İşte bir örnekleme var:

1. pumping lemma for regular languages kullanın. Bu, dillerin düzenli olmadığını kanıtlamak için en çok öğretilen tekniktir. Sipser'in bir kopyasının bulunduğunu ve Bölüm 1'de konuyla ilgili iyi bir tedavi yaptığını belirttiniz.

2. Myhill-Nerode theorem'u kullanın. Bu güçlü teorem, pompalama lemmalarından kafanızı sarmaktan biraz daha zorlayıcıdır, ancak dilleri kanıtlamak için bir araç olarak çift-görevli değildir ve düzensiz dilleri koklamak için kullanabileceğiniz mükemmel bir sezgi sağlar. (Bu, öğrencilerimi CS teorisine girişimde öğrettiğim tekniktir). Bağlı slaytlar, {a ⁿ b ⁿ | N} 'de n, her ikisi de ilk prensiplerden ve Myhill-Nerode kullanarak düzenli değildir.

3. closure properties of regular languages'u kullanın. Düzenli dilleri normal dillerle eşleyen belirli bir işlemi uyguladıktan sonra, düzensiz bir dil ile sonuçlandığını kanıtlayarak bir dilin düzenli olmadığını sık sık gösterebilirsiniz. Sağladığınız örnekler üzerinde Looking

, ben pompalama lemma (1) nonregular olduğunu dili kanıtlayan en kolay yolu olacağını düşünüyoruz. Myhill-Nerode teoremi, (3) ve (4) 'ün kısa çalışmalarını yapmalıdır. (2), dille kesişimini ve b ^☆ bir ^☆ b ^☆ alarak düşünebilirsiniz için, daha sonra Myhill-Nerode veya sonuçlanan dile pompalama Lemmasını uygulamak.