Python Programming

Task 2: Writing regular expressions

Write regular expressions for the following languages. Test your regular expressions using re.match().

[Credits: Q1, 2 and 4 are adapted from Speech and Language Processing, Jurafsky & Martin]

Question 1

Write a regular expression for the set of all alphabetic strings.

• Valid: cake, HeLLo WorLd, Llanfairpwllgwyngyllgogerychwyrndrobwllllantysiliogogogoch, empty string
• Invalid: 123, backstreet_boys, mamboNumber5

Question 2

Write a regular expression for the set of all lower case alphabetic strings ending in a "b".

• Valid: bob, climb, door knob
• Invalid: Bob, britney spears, WANNABE

Question 3 (Upping the difficulty!)

Write a regular expression for the set of lowercase letters where there must be an "a" at every odd position in the string.

• Valid: a, aca, aaaba, acafa, aaaaaa, empty string
• Invalid: b, baba, acda, aeaaf

Question 4 (Challenge!)

Write a regular expression for the set of all strings from the alphabet {a,b} such that each "a" is preceded by and immediately followed by a "b".

• Valid: bab, babbab, bababababab, bbbabbbbbbabb, bbbb, bb, b, empty string
• Invalid: a, abba, bbaba, aaa

Hint: This one might be a bit tough! Like programming, break this down into smaller subproblems! Try covering the simplest case first (empty string), then add in the "b"s (without "a"s, which is valid), then include the cases with "a" while satisfying the "bab" constraint.