AAG 1

Description

Mind Map on AAG 1, created by Šabata Tomáš on 05/29/2014.
Šabata Tomáš
Mind Map by Šabata Tomáš, updated more than 1 year ago
Šabata Tomáš
Created by Šabata Tomáš over 10 years ago
48
0

Resource summary

AAG 1
  1. Jazyk L

    Annotations:

    • Množina všech přípustných kombinací znaků vstupní abecedy
    1. Rekurzivně spočtěné

      Annotations:

      • \( \alpha\) -> \(\beta \)
      1. Kontextové

        Annotations:

        • \( \alpha B \gamma \) -> \( \alpha \beta \gamma\)
        1. bezkontextové

          Annotations:

          • A->\(\alpha\)
          1. regulární

            Annotations:

            • A -> aB | a S -> eps (pokud jazyk generuje prazdné slovo) 
            1. Konečný automat
            2. Zasobníkový automat
            3. lin. omezený TS
            4. TS
          2. Pumping lemma

            Annotations:

            • Obecně nejde dokázat, že je jazyk regulární, lze to pouze vyvrátit, když není.
            1. Důkaz sporem
              1. Regulární jazyk ==> platí pumping lemma
              2. definice pro Regulární Jazyk
                1. slovo w ∈ L && |w| >=p
                  1. w = x y^i z
                    1. 1<=|y| && |xy|<p && i>=0
                    2. definice pro Bezkontext. jazyk
                      1. w = x u^i y v^i z
                        1. 1<=|uyv|<p && i >=0
                      Show full summary Hide full summary

                      Similar

                      OCR Chemistry - Atoms, Bonds and Groups (Definitions)
                      GwynsM
                      Question Words - GCSE German
                      lucykatewarman1227
                      21 Random IT questions
                      Eden Goddard
                      Sociology- Family and Households Flashcards
                      Heloise Tudor
                      The Brain and the Nervous System
                      feelingthepayne
                      Personality disorders
                      Anna Walker
                      Biology B2.2
                      Jade Allatt
                      SCLY1 - Families and Households theorists - Topic 1 Couples quiz (AQA AS sociology)
                      Tahlie
                      AQA Biology B2 Questions
                      Sian Griffiths
                      The Biological Approach to Psychology
                      Gabby Wood
                      Ahmed has tremors
                      Fatima Alkhateeb