Gramatiky, odvozování
Příklad 1
Mějme gramatiku G = ({S, A, B}, {a, b, c}, P, S), kde množina pravidel P je následující:
S → aS | bS | cA
A → aA | bA | cB | ε
B → aB | bB | cS
Úkoly:
• Zapište odvození slov abc, acbabb, acbccbc v gramatice G.
• Napište všechna slova, která gramatika G vygeneruje maximálně ve 3 krocích. [Mají být 4]
• Napište všechna slova w délky maximálně 3, která je gramatika G schopna generovat.[Má
jich být 17]
• Napište všechna slova w délky 4, která je gramatika G schopna generovat. [Má být pouze 1]
• Zkuste říct, jaký jazyk generuje gramatika G.
Příklad 2
Mějme gramatiku G = ({S, A, B, C}, {a, b}, P, S), kde množina pravidel P je následující:
S → aA | bB
A → aS | bC
B → aC | bS
C → aB | bA | ε
Úkoly:
• Zapište odvození slov ab, ba, abaa, abbaba v gramatice G.
• Napište všechna slova, která gramatika G vygeneruje maximálně ve 3 krocích. [Mají být 2]
• Napište všechna slova w délky maximálně 4, která je gramatika G schopna generovat.[Má
jich být 10]
• Zkuste říct, jaký jazyk generuje gramatika G.
1
Příklad 3
Nalezněte gramatiky generující následující 3 jazyky:
1. L1 = {w ∈ {a, b, c}∗ | w obsahuje podslovo bca}
2. L2 = {w ∈ {a, b, c}∗; |w| = 3k + 2, k ∈ N0}
3. L3 = {w ∈ {a, b, c}∗ | a(w) > 0 ∧ c(w) > 1}
Poznámka: Zápis x(w) znamená počet symbolů x ve slově w.
2