Tutorial Week 4 (Solutions)
Task 1.This one is very simple.
• 16 * 17 *
• / \ = 272
• 16 17
•
• 2 + 3 + 4 + +
• / \ / \
• + 4 = 9 , 2 + = 9
• / \ / \
• 2 3 3 4
•
• 2 * 3 + 4 * 5 *
• / \
• 2 +
• / \ = 46
• 3 *
• / \
• 4 5
•
•
• *
• / \
• 2 *
• / \ = 70
• + 5
• / \
• 3 4
•
• +
• / \
• * * = 26
• / \ / \
• 2 3 4 5
•
•
• *
• / \
• + 5
• / \
• * 4 = 50
• / \
• 2 3
•
•
• *
• / \
• * 5
• / \
• 2 + = 70
• / \
• 3 4
•
Task 2.
• ((01*0) | (1(00)*1))? S → ε | A | B
• A → 0A’0
• A’ → 1A’ | ε
• B → 1B’1
• B’ → 00B’ | ε
•
• ((01*0) | (1(00)*1))+ S → A | AS
• A → B | C
• B → 0B’0
• B’ → 1B’ | ε
• C → 1C’1
• C’ → 00C’ | ε
•
• Palindromes over {0, 1} are generated by: S → ε | 0S0 | 1S1 | 0 | 1
•
• The language given by the regular expression 0*1* with the additional constraint that there must be more 0s than 1s. S -> 0S | 0T
• T -> 0T1 | epsilon
•