Regular Languages

4.4.2.4 (12 questions). Public Notes: AQA's A Level Computer Science

Within a regular expression what does this metacharacter mean "*".

0 or more repetitions: ab* is {a, ab, abb, abbb …}

Within a regular expression what does this metacharacter mean "+".

1 or more repetitions: c*d is {cd, ccd, cccd…}

Within a regular expression what does this metacharacter mean "?".

Previous character optional: Colou?r is {Colour, Color}.

Within a regular expression what does this metacharacter mean "|".

alternative, on or the other but not both: previous character could be...e|f is {e, f}

Within a regular expression what does this metacharacter mean "()".

Grouping of regular expressions(ab)|(cd)e is {abe, cde}.

Describe the relationship between FSM and regular expressions.

For each regular expression, there is an equivalent FSM.

Draw the FSM machine for this regular expression "a|b"

image

"Draw the FSM machine for this regular expression "a+"

image

Draw the FSM machine for this regular expression "a*"

image

Draw the FSM machine for this regular expression "ab"

image

Draw the FSM machine for this regular expression "(abc*)|(d+e)"

image image

Define regular language

A language is regular if it can defined with a FSM.