Eksamen

Question 1

If a language is context-free, is it then regular?

Answer 1

No.

Question 2

Signs that a language is context-free:

Answer 2

• 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 | ɛ

Question 3

Signs that a language is regular:

Answer 3

• You can describe it with a DFA or a NFA.
• You can describe it with a regular expression.

Question 4

What can be in Chomsky-normal-form?

Answer 4

All context-free grammars/languages.

Question 5

Can every:

pushdown-automata

be converted to a

deterministic pushdown-automata?

Answer 5

No.

Question 6

Signs that a language isn’t regular.

Answer 6

• 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)

Question 7

List the four kinds of scope rules:

Answer 7

1. Full Static scope rules
2. Full Dynamic scope rules
3. Mixed where envV is static and envP is dynamic
4. Mixed where envV is dynamic and envP is static

Question 8

Dynamic scope rules are:

Answer 8

When the environtment from call time is used

Question 9

Static scope rules are:

Answer 9

When the environtment from declaration time is used

Question 10

What are the three most common parameter mechanisms?

Answer 10

1. Call by value.
2. Call by reference.
3. Call by name.

Question 11

What is call/pass-by value?

Answer 11

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;

Question 12

What is call/pass-by reference?

Answer 12

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

Question 13

What is call/pass-by name?

Answer 13

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).

Question 14

Which operations are regular languages closed under?

Answer 14

complement (A’),

intersection(A ∩ B),

union(A U B),

concatenation(A o B),

Kleene star A*

Question 15

What does Σ (Sigma) describe?

Answer 15

It describes an alphabet.

An alphabet is a finite set of symbols.

Question 16

What is δ? (Delta)

Answer 16

The transition function.

Q x Σ –> Q (describes which state you go to and from with a given input.)

Question 17

What is the definition of a Finite Automaton? (which tuples does it contain)

Answer 17

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.)

q₀ = Initial state

F = Final set of states

Question 18

How to define a language

Answer 18

1. Med en grammatik; Productions ( S= aSa | epsilon; )
2. Hvis regulært: regular expressions (problematisk)
3. Definition, setup og regler: L(M₁) = { w ∈ {0, 1} | extra rules }

Question 19

What is the pumping length?

Answer 19

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.

Question 20

Regular expression pumping:

What are the conditions xyz must satisfy for the language to be regular?

Answer 20

w = xyz

xyⁱz is in the language for all “i ϵ N(natural numbers)” (no matter what “i” is xyⁱz is in the language)

xz can always be ɛ.

|y| > 0 (cannot be ɛ)

|xy| ≤ p

Question 21

What are the 4 steps in the game with the Demon?

Answer 21

• 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 xy^_iz in the best possible way for him
  4. I choose i that must be at least zero.

Question 22

What is a derivation?

Answer 22

=> 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”.

Question 23

What is the definition of a grammar?

Answer 23

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;*

Question 24

What is the definition of a context-free grammar?

Answer 24

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.

Question 25

How do you convert a DFA into a CFG?

Answer 25

Turn the states: q₀, q₁, q₂, q₃ into rules: R₀, R₁, R₂, R₃

By looking at the automata transition function (δ(delta)) you can directly translate it into a rule.

Question 26

How would you prove that a phrase is ambiguous?

Answer 26

Create 2 different and valid parse trees from the phrase.

Question 27

When is a Context-Free Grammar in Chomsky Normal Form?

Answer 27

When just one of these rules are fulfilled for all productions:

A -> BC (when the nonterminal A becomes two nonterminals)*

A -> a (when the nonterminal A becomes one terminal)*

S -> ɛ (s is the only symbol allowed to be epsilon)

*any nonterminal can only be two nonterminals or one terminal

Question 28

How is the transition represented on a PDA model

Answer 28

(input, pop) -> push

Question 29

What does SOS stand for?

Answer 29

Structural Operational Semantics

Question 30

What are the two types of Structural Operational Semantics? (SOS)

Answer 30

Big-Step semantics

Small-Step semantics

Question 31

What is a tuple?

Answer 31

A chain of functions that uses eachothers outputs, that acts as one function.

E.g.

A() returns x, x is used as input in B(x), y is the output of B and is used as the input of C(y)

Question 32

Define an Equivalence relation:

Answer 32

R is an equivalence relation if A is nonempty and R is reflective, symmetric and tranitive.

E.g.

x ≡_myRelation y if specifiedConditions.

Question 33

An equivalence relation is reflective if:

Answer 33

If the equivalence relation is used to compare something with itself and it returns true if they are the same.

E.g.

A ≡_customName A

If it evaluates A to be the same as itself it is reflective. (They are almost always reflective)

Question 34

An equivalence relation is symmetric if:

Answer 34

If the equivalence ≡_myRelation specifies that:

if x = y then y = x

Then ≡_myRelation is symmetric

Question 35

An equivalence relation is transitive if:

Answer 35

if ≡_myRelation specifies that if:

x = y and y = z then x is also = z

Question 36

Context-free pumping:

What are the conditions of uvxyz?

Answer 36

uxz can always be ɛ.

|vy| > 0 (only one of them can be ɛ)

|vxy| ≤ p

if uvⁱxyⁱz = w then w ∈ L for i ∈ N

Question 37

What does GNFA mean and are the rules for its states?

Answer 37

A generalized nondeterminstic finite automaton.

1. Start state:
   
   1. Arrows pointing at every other state.
   2. No arrows pointing at it.
2. Final state
   
   1. Only one final state.
   2. Arrows pointing at it from every other state.
   3. No arrows pointing from it.
3. Regular states
   
   1. Has to point to the final state.
   2. Has to point to every other regular state.
   3. Has to point to itself.

Question 38

Hieracy of grammar, languages and automatas.

Answer 38

Question 39

Context-free pumping:

How do you describe the pumping process in the exam? (without mentioning the demon)

Answer 39

1. Assume L to be a context-free language.
2. Let p ≥ 0 be a pump length for L and select a string s ∈ L so that |s| ≥ p.
3. Show for any split of s of the form uvxyz that it does not comply with the conditions 1-3 of the Pumping Lemma, i.e., that we do not have
   
   1. uvⁱxyⁱz ∈ L for i ∈ N
   2. |vy| > 0
   3. |vxy| ≤ p
4. Therefore we can conclude that L is not context-free.

Question 40

What is the definition of a PDA?

Answer 40

A PDA is a touple: P = (Q, Σ, δ, γ, q₀, F)

Q = finite set of states.

Σ = finite alphabet.

δ (delta) = transition function.

γ = finite stack alphabet.

q0 = initial state.

F = finite set of final states.

Question 41

What is the definition of a GNFA?

Answer 41

A GNFA is a touple (Q, Σ, δ, q_s. q_a)

Q = finite set of states

Σ = finite input alphabet

δ = transition function

q_s = start state

q_a = final state