Exam Questions

Question 1

How to count occurances with DFA?

Answer 1

1. Creat a path following the sequence, ensure that if completed it remains in the same position
2. For any deviation, check where in the word it occurs. If it lands nowhere, go back to the start
3. Ceck if needs to be consequtive or exact

Question 2

How to minimize a DFA?

Answer 2

1. Remove all unreachable states
2. Create a partitioning s.t. {{ final states }, { other states }}
3. Look if there is a partition, that if you go from the partition to any other partition, it can be split. Repeat until no more splits are possible
4. Then create the graph from these partitions

Question 3

How to convert NFA to DFA?

Answer 3

When converting from NFA to DFA, we’re basically suggesting in which state the NFA can be. Likely you’ll be able to check these types of questions partially

Question 4

How to convert Right linear grammar to Strictly right linear grammar?

Answer 4

A strictly right linear grammar has at most 1 variable (i.e., a capital letter),

Note: you are allowed to have lambda rules

Question 5

How to go from strictly right linear grammar to NFA (graph)?

Answer 5

1. Start a starting variable & create variable F.
2. Then do the following:

• For every A -> B, make a transition lambda from A to B.
• For every A -> aB, make a transition a from A to B
• For every A->a, make a transition a from A to F.

Question 6

How to go from NFA (graph) to regular expression?

Answer 6

This is clearly explained in the cheat sheet.

Question 7

How to remove lambda productions?

Answer 7

1. Just create a list of all variables that can be lambda.
2. Then create a copy of the rule but without an empty variable.

Question 8

How to remove unit production rules?

Answer 8

Just when you see an assignment with a unit production rule, replace it with an instruction from the unit.

Question 9

How to remove useless variables?

Answer 9

1. Identify non-reachable variables
2. Identify non-productive variables. (i.e., variables that always refer to themselves).
3. Identify all useless variables
   * All variables named before
   * All variables only in a rule named before

Question 10

How to rewrite to Chomsky Normal form?

Answer 10

1. For every character: create a new variable
2. Split all variables s.t. they have a maximum length 2.

Question 11

How to use CYK parsing?

Answer 11

1. Start with V_a = {...}, which contains all variables that generage a.
2. Continue enlarging the sets for new combinations, which might be in your word.

Question 12

How to do LL(1) parsing?

Answer 12

Parsing from a table:
1. Look at the first letter, choose the accompanying rule.

Creating a table:
1. Find the letters each variable can start with (start from the simples to the hardest).
2. Find all the letters that can follow each variable. (e.g., A->aBc implies c in Follow(B)).
3. Fill in the table, thinking: “If I were to read A, and you would see this letter, which rule am I reading?”

Question 13

How to fo from NPDA to Context Free?

Answer 13

1. Start with 1 ->2, with rule a[b/lambda]. Write these as (1, b, 2) -> a.
2. Continue with 1->2, with rule a[b/c]. Write as: for all r1: (1, b, r1) -> a(2,c,r2)
3. Move on with 1->2, with rule a[b/cd]. Write as: for all r1, r2: (1, b, r2) -> a(2, c, r1)(r1, s, r2).
4. Etc.