Regular languages common mistakes

Common mistakes

• Putting Mealy outputs on states

  Writing the output inside a state or treating it as an output of the state itself.

  Fix itFor a Mealy machine, place or record the output on the transition, alongside the input, because the output is produced when that transition is taken.

• Treating a set as ordered

  Assuming that changing the order of elements creates a different set, or counting repeated values more than once.

  Fix itRemember that a set is unordered and each value occurs at most once. For example, writing an element twice does not create an additional distinct element.

• Misreading the scope of *

  Treating a* as meaning that the whole expression can be repeated, rather than just the preceding a.

  Fix itRemember that * applies to the immediately preceding regular expression. Use parentheses, such as (a|b)*, when the repetition should apply to a group.

• Confusing regular languages with programming languages

  Assuming that a language is regular because it is written in Python, Java, C# or VB.NET.

  Fix itJudge regularity using the specification: the language must be representable by a regular expression or be accepted by an FSM.