2024 JAN/FEB COS3701
Unofficial memo
, Question 1
a) Determine a regular expression for the language L over the alphabet {a, b}
that ends with a letter that is different from the letter that it starts with. For
example, ab, ababab and aaaaabaaaabbbbbb are words in L but aaa, baabbaab,
aaaaabaaaaaa and abaa are not.
(a(a+b)*b) + (b(a+b)*a)
b) Design a deterministic finite automaton (DFA) that will recognise all of the
words in as defined above.
c) Use Theorem 21 to develop a context-free grammar (CFG) for the language
L.
CFG
S → aA | bB
A → aA | bC
B → bB | aD
C → aA | bC | Λ
D → aD | bB | Λ
Unofficial memo
, Question 1
a) Determine a regular expression for the language L over the alphabet {a, b}
that ends with a letter that is different from the letter that it starts with. For
example, ab, ababab and aaaaabaaaabbbbbb are words in L but aaa, baabbaab,
aaaaabaaaaaa and abaa are not.
(a(a+b)*b) + (b(a+b)*a)
b) Design a deterministic finite automaton (DFA) that will recognise all of the
words in as defined above.
c) Use Theorem 21 to develop a context-free grammar (CFG) for the language
L.
CFG
S → aA | bB
A → aA | bC
B → bB | aD
C → aA | bC | Λ
D → aD | bB | Λ
