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
MBS Real Studio Plugins
