Quiz zur Vorlesungsnachbereitung

Quiz 1: ableitbares Wort einer kontextfreien Grammatik

Gegeben seien die folgenden Regelmengen einer kontextfreien Grammatik, jeweils mit dem Start-Symbol Start. Mit welchen dieser Grammatiken ist das Wort aaa ableitbar?

{Start -> Start,    Start -> a}

{Start -> Start a,    Start -> a}

{Start -> Start aaa,    Start -> a}

{Start -> Start,    Start -> aaa}

{Start -> A,    A -> bB,     B -> A | aaa}

Quiz 2: erzeugte Sprache einer kontextfreien Grammatik

Gegeben seien die folgenden Sprachen und die nachfolgenden Regelmengen einer kontextfreien Grammatik, jeweils mit dem Start-Symbol Start. Welche der Sprachen werden durch die angegebene Grammatik erzeugt?

L = {aⁿ | n >= 0}

{Start -> a Start,    Start -> a}

L = {aⁿ | n >= 2}

{Start -> Start a,    Start -> aa}

L = {aⁿbⁿ | n >= 1}

{Start -> Start b,    Start -> a Start,    Start -> ε}

L = {aⁿb^m | n > m}

{Start -> Start b,    Start -> a Start,    Start -> a}

L = {ε}

{Start -> A,    A -> bB,    B -> A | aB}

Quiz 3: mehrdeutige kontextfreie Grammatik

Welche der folgenden Grammatiken sind mehrdeutig?

{Start -> a Start | Start a,    Start -> a}

{Start -> Start a | A,    Start -> a,    A -> a}

{Start -> AB,    A -> aA | b,    B -> bB | ε}

{Start -> Start bb | bB,    B -> bb Start | b}

{Start -> A | B,    A -> aA | B,    B -> A | aB}