Theoretische Informatik

Grammatik zu a^n^2

Beispielwörter:
n = 0 -> ε
n = 1 -> a
n = 2 -> aaaa
n = 3 -> aaaaaaaaa

aQuadrat2 = (V, T, R, S)

T = { a, b }
V = { S, A, B, C, D, E, F }
R = {
        S -> AabBE | a | ε
        BE -> bbCE      // Nach links laufen mit C
        bC -> Cab
        aC -> Ca
        AC -> F         // ab F machen wir nur noch Terminale
        Fa -> aF
        Fb -> F         // b weg
        FE -> ε
        AC -> AD        // Rücklauf mit D
        Da -> aD
        Db -> bD
        DE -> BE
}

Beispiel:

        S
=>      AabBE           	// ab hier 1 a
=>      AabbbCE
=> *    ACaabababE      	// ab hier 4 a
=>      ADaabababE
=> *    AaabababDE
=>      AaabababbbCE
=> *    ACaaabaabaabababE 	// ab hier 9 a
=>      FaaabaabaabababE 	// mit dem F kommen wir dann zum Ende
=>      aaaaaaaaaFE
=>      aaaaaaaaa

Beschränkte Grammatik zu a^n^2

aQuadrat2b = (V, T, R, S)

T = { a, b }
V = { S, A, B, C, D, E, F }
R = {
        S -> AbBE | aaaa | a | ε
        BE -> bbCE      // Nach links laufen mit C
        bC -> Cab
        aC -> Ca
        AC -> aF        // ab F machen wir nur noch Terminale
        Fa -> aF
        Fb -> aF        // b weg
        FE -> aa
        AC -> AD        // Rücklauf mit D
        Da -> aD
        Db -> bD
        DE -> BE
}

Beispiel:

n = 0
        S
=>      ε

n = 1
        S
=>      a

n = 2
        S
=>      aaaa

n = 3
        S
=>      AbBE 
=>      AbbbCE
=>      AbbCabE
=>      AbCababE
=>      ACabababE      
=>      aFabababE
=>      aaFbababE
=>      aaaFababE
=>      aaaaFbabE
=>      aaaaaFabE
=>      aaaaaaFbE
=>      aaaaaaaFE
=>      aaaaaaaaa	// 9 a

n = 4
        S
=>      AbBE 
=>      AbbbCE
=>      AbbCabE
=>      AbCababE
=>      ACabababE      
=>      ADabababE
=> *    AabababDE
=>      AabababbbCE
=> *    ACaabaabaabababE
=>      aFaabaabaabababE
=>      aaaaaaaaaaaaaaFE
=>      aaaaaaaaaaaaaaaa	// 16 a

n = 5
        S
=>      AbBE 
=>      AbbbCE
=>      AbbCabE
=>      AbCababE
=>      ACabababE      
=>      ADabababE
=> *    AabababDE
=>      AabababbbCE
=> *    ACaabaabaabababE
=>      ADaabaabaabababE
=> *    AaabaabaabababDE
=>      AaabaabaabababbbCE
=> *    ACaaabaaabaaabaabaabababE
=>      aFaaabaaabaaabaabaabababE
=>      aaaaaaaaaaaaaaaaaaaaaaaFE
=>      aaaaaaaaaaaaaaaaaaaaaaaaa	// 25 a

Grammatik zu a^n b^n c^n d^n

Beispielwörter:
n = 0 -> ε
n = 1 -> abcd
n = 2 -> aabbccdd
n = 3 -> aaabbbcccddd

abcd = (V, T, R, S)

T = { a, b }
V = { S, A, B, C, D, E, F }
R = {
        S -> FAAAABBBBCCCDL | aaabbbcccddd | aabbccdd | abcd | ε
        F -> FABCD
        F -> G // am Ende
        DA -> AD 
        DB -> BD 
        DC -> CD 
        CA -> AC 
        CB -> BC 
        AB -> BA 
        GA -> AG 
        GB -> BH 
        HB -> BH 
        HC -> CI
        IC -> CI 
        ID -> DJ
        JD -> DJ
        JL -> DDD
        A -> a
        B -> b
        C -> c
        D -> d
        
        
}

Beispiel:

        S
=>      FAAAABBBBCCCDL       	
=>		FABCDAAAABBBBCCCCDL
=>		GABCDAAAABBBBCCCCDL
=> *	GABCAAAADBBBBCCCCDL
=> *	GABCAAAABBBBDCCCCDL
=> *	GABAAAABBBBCCCCCDDL
=> *	GAAAAABBBBBCCCCCDDL
=> *	AAAAAGBBBBBCCCCCDDL
=>  	AAAAABHBBBBCCCCCDDL
=> * 	AAAAABBBBBHCCCCCDDL
=>  	AAAAABBBBBICCCCCDDL
=> * 	AAAAABBBBBCCCCCIDDL
=>  	AAAAABBBBBCCCCCDJDL
=>  	AAAAABBBBBCCCCCDDJL
=>  	AAAAABBBBBCCCCCDDDDD
=> *  	aaaaabbbbbcccccddddd




Links
Bilder aus Nickenich

In Erinnerung and den lächelnden Mac Plus, den man beim Start von Mac OS 1 bis X.1 sieht...