Top-down oder Bottom-up

Ein Bottom-Up-Automat ($ \Sigma$, Q, F, R) heißt deterministisch, wenn in R alle linken Regelseiten verschieden sind.

Ein Top-Down-Automat ($ \Sigma$, Q, F, R) heißt deterministisch, wenn?

Es gibt Baumsprachen, die einen deterministischen bottom-up-, aber keine deterministischen top-down-Automaten besitzen.



Johannes Waldmann 2006-02-02