Quizzes Flashcards
In a Chomsky Hierarchy, what automata(acceptors) go with each level?
Type 0: Turing Machine
Type 1: linear bounded
Type 2: push-down automata
Type 3: finite automata
Definition of a Grammar
4-Tuple:
(V, Σ, R, S): Set of non-terminals, terminals, set of productions, start symbol
A computational machine is considered non deterministic if a given current state and an input symbol, there is exactly one choice for the next state.
False
What is the order of the RE to mDFA pipeline
RE → Thompson’s Construction → NFA → Subset construction → DFA → Hopcroft’s Algorithm →mDFA
A syntax tree is an ordered, rooted tree that represents the syntactic structure of a string of sentence generated by a formal grammar.
True
What are the two types of top-down parsers (discussed in class)
Recursive descent, predictive
What is left recursive grammar?
A grammar containing productions of form A → Aα
Left derivation
Process of generating a string by replacing at each step the left-most non-terminal
A context-free language that is generated by no unambiguous grammar is:
Inherently ambiguous
Follow set
If A is a non terminal, then it is the set of terminals that can follow A in some sentential form
First set
If α is a sentential form, then it is the set of terminals that can begin a string derived from α
Broadly, what does a parser need in order to do its job?
Production rules, token stream, stack
What are the grammars at each level of Chomsky’s hierarchy? Can also be asked as what are the production rules?
Type 0: α → β
Type 1: αAβ → αγβ
Type 2: A → α
Type 3: A → aA, A → a
What are the different LR grammars?
LR, LLR, LALR, GLR, CLR, SLR
It is easy to generate bottom up parsing by hand T/F
False
