Eksamen Flashcards
(41 cards)
If a language is context-free, is it then regular?
No.
Signs that a language is context-free:
- You can describe it with a PDA.
- You can describe it with a context-free grammar:
E.g. we have the language (c | ɛ) a (c | ɛ) b
(c | ɛ) can be made into a non-terminal called C.
S -> CaCb
C -> c | ɛ
Signs that a language is regular:
- You can describe it with a DFA or a NFA.
- You can describe it with a regular expression.
What can be in Chomsky-normal-form?
All context-free grammars/languages.
Can every:
pushdown-automata
be converted to a
deterministic pushdown-automata?
No.
Signs that a language isn’t regular.
- By using the pumping lemma. (It is hard to do if you don’t know that it isn’t regular) (Often used to prove that it isn’t regular not so much to find out if it isn’t regular)
List the four kinds of scope rules:
- Full Static scope rules
- Full Dynamic scope rules
- Mixed where envV is static and envP is dynamic
- Mixed where envV is dynamic and envP is static
Dynamic scope rules are:
When the environtment from call time is used
Static scope rules are:
When the environtment from declaration time is used
What are the three most common parameter mechanisms?
- Call by value.
- Call by reference.
- Call by name.
What is call/pass-by value?
The actual parameter is evaluated at call time.
E.g.
int func(a) { return a + 1 }
func(2 + 3)
Behind the scenes this happens: a = 5
So the return statement reads return a + 1;
What is call/pass-by reference?
No new variable is declared at call-time, instead the parameter is used directly.
E.g.
int x = 2 + 3;
int func(a) { a = a + 1; }
func(x);
Print(x); // x = 6
What is call/pass-by name?
The parameter passed isn’t evaluated before it is used in the function.
E.g
int func(a) { return a + 1; }
func(2 + 3)
The return statement in the body of func will read
return 2 + 3 + 1
instead of
return a + 1; (call by value).
Which operations are regular languages closed under?
complement (A’),
intersection(A ∩ B),
union(A U B),
concatenation(A o B),
Kleene star A*
What does Σ (Sigma) describe?
It describes an alphabet.
An alphabet is a finite set of symbols.
What is δ? (Delta)
The transition function.
Q x Σ –> Q (describes which state you go to and from with a given input.)
What is the definition of a Finite Automaton? (which tuples does it contain)
Q = is a finite set of states.
Σ = is a finite alphabet.
δ = Transitions: Q x Σε –> P(Q). (describes which state you go to and from with a given input.)
q0 = Initial state
F = Final set of states
How to define a language
- Med en grammatik; Productions ( S= aSa | epsilon; )
- Hvis regulært: regular expressions (problematisk)
- Definition, setup og regler: L(M1) = { w ∈ {0, 1} | extra rules }
What is the pumping length?
A natural number p ≤ |w|
A natural number, p, for a regular laguage for which it is true that any word in the language longer than p, can be pumped.
Regular expression pumping:
What are the conditions xyz must satisfy for the language to be regular?
w = xyz
xyiz is in the language for all “i ϵ N(natural numbers)” (no matter what “i” is xyiz is in the language)
xz can always be ɛ.
|y| > 0 (cannot be ɛ)
|xy| ≤ p
What are the 4 steps in the game with the Demon?
- You play a game against a demon. The demon tries to prove the language is regular. You try to disprove it.*
1. Demon chooses p (You don’t know it usually)
2. I choose a word (that must have at least p length, usually define by using p)
3. Demon splits w into xyiz in the best possible way for him
4. I choose i that must be at least zero.
What is a derivation?
=> without star means that you are not allowed to dig deeper.
E.g: The grammar: A -> B | AA | epsilon, B -> a | b ;
A => aba, means can you get “aba” from A where you don’t dig deeper. Since “a” and “b” are in B you can not access it from A without going futher.
=>* with star means that you are allowed to go futher.
E.g The grammar from above.
A=>* aba is allowed since from A you can go to B and find “a” and “b”.
What is the definition of a grammar?
It is a tuple consisting of G = ( V, Σ, R, S )
- V is a finite set of variables / nonterminals*
- Σ is a finite set of terminals*
- R is a finite set of rules (a variable and a string)*
- S is the start variable*
Example of a grammar:
- S -> aA ;*
- A -> aa;*
What is the definition of a context-free grammar?
A grammar where all production rules (Nonterminal -> something) can be applied regardless of the context, in other words there are no conditions to when a rule can be used.
It is the opposite of a context-sensitive grammar.
