Regular Expressions
Regular expressions for GATE CS: the six building blocks, operator precedence, the identities that hold (with the empty set and epsilon cases) and the look-alikes that fail with their shortest counterexample, writing expressions for described languages such as no two consecutive a's or number of a's divisible by 3, testing two expressions for equivalence, and counting the strings of a given length. Every identity and construction was checked on all strings over {a, b} up to length 9.
