BI-AAG cvičení 3

Označte pravdivá tvrzení

• RG⊆BG⊆KG⊆NG

• RJ⊆BJ⊆KJ⊆RSJ

• RJ⊆BJ⊄KJ⊆RSJ

• RG⊆BG⊄KG⊆NG

Který jazyk generuje následující gramatika?

G = ({S, A, B}, {a, b}, {S->aSb | A | B, A -> aA | a, B-> bB | b}, S)

• L(G)={a^i . b^j : i ≠ j}

• L(G)={a^i . b^j : i ≥ j}

• L(G)={a^i . b^j : j ≥ i}

Které pojmy vyjadřují stejnou věc jako větná forma?

• slovo

• řetězec

• string

• věta

• žádná z ostatních možností není správná

Pro které jazyky vždy existuje konečný automat, který je přijímá?

• Kontextové jazyky

• Bezkontextové jazyky

• Regulární jazyky

• Rekurzivně spočetné jazyky

Nechť L je konečný jazyk, určitě platí:

• L je regulární

• L je bezkontextový

• L je kontextový

• L je rekurzivně spočetný