Formal Languages Flashcards
(15 cards)
What is a type-0 grammar?
Every grammar is automatically type 0 and there are no restrictions on their production rules.
What is a type-0 grammar also known as?
Recursively enumerable.
What is a type-1 grammar?
A grammar is type 1 if for all production rules w1 -> w2 the length of w1 is less than or equal to w2.
What is a type-1 grammar also known as?
Context sensitive
What is a type-2 grammer?
A type 1 grammar is type-2 if for all production rules w1 -> w2, w1 is a single non-terminal symbol
What is a type-2 grammar also known as?
Context free
What is a type-3 grammar?
A type-2 grammar is type-3 if for all production rules w1 -> w2, w2 is either a single terminal symbol or a terminal symbol followed by one non-terminal symbol.
What is a type-3 grammar also known as?
Regular
What is the special case for the empty word?
If having the empty is desirable, then S -> (empty word) can be added as long as S is not part of a production rule body.
What is the word problem?
The problem of deciding if for a given language L and a given word w the property w belong to L holds.
What is a Turing machine?
The most basic version of a computer consists of a tape of infinite length, separated into fields that can contain a value. These fields are read and written to by a head that moves along the tape.
What is the formal definition of a turing machine?
A Turing machine the the 7-tuple:
M = (Q, Sigma, Gamma, delta, q0, [], F)
What is a Linear Bounded Automaton?
An LBA is a Turing machine that is bounded by the input side.
Which languages are accepted by LBA’s?
Type-1 (context sensetive) languages
