Automata theory Q1

Hierarchy of languages is introduced by

• Noam Chomsky

• Alan Turing

• Steve Kleen

• Cook

Equivalent automata that accepts regular language is

• Turing Machine

• Linear Bounded Automata

• Push Down Automata

• Finite Automata

Equivalent automata that accepts context free language is

• Turing Machine

• Linear Bounded Automata

• Push Down Automata

• Finite Automata

Equivalent automata that accepts context sensitive language is

• Turing Machine

• Linear Bounded Automata

• Push Down Automata

• Finite Automata

Equivalent automata that accepts recursive enumerable language is

• Turing Machine

• Linear Bounded Automata

• Push Down Automata

• Finite Automata

Turing machine is a powerful model that accepts all languages.

• True

• False

A___________ is a collection of sentences of finite length all constructed from a finite alphabet of symbols.

• string

• word

• language

• alphabet

Type 0 grammar is otherwise called as ________.

• Recursively Enumerable Language

• Context Sensitive language

• Context free language

• Regular language

Type 3 grammar is otherwise called as _________.

• Regular Language

• Recursive Language

• Context Free language

• Context Sensitive language

Type 1 grammar is otherwise called as ___________.

• Context Free Language

• Context Sensitive Language

• Regular Language

• Recursive Language