Correctionclarification Note that the transition from Rb to

Correction/clarification: Note that the transition from Rb,? to n, which had been

unlabeled, is only taken when a ? occurs before a b as the read/write head moves

right.

2. (4 points) The diagram below is macro notation for a TM M with ?={a,b}, ? = {a,b,$,#,?}, and H = {y,n}. \"v\" is used to represent the endpoint of a down arrow. Give a short English description of the language accepted by M.

Solution

he patterns, or regular expressions, over an alphabet that we will use.
Each such regular expression, r, represents a whole set (possibly an infinite set) of strings
in

that match r. The precise definition of this matching relation is given on Slide 6. It
might seem odd to include a regular expression that is matched by no strings at all—but it
is technically convenient to do so. Note that the regular expression is in fact equivalent to


, in the sense that a string u matches

iff it matches (iff u = ).
Regular expressions over an alphabet
• each symbol a is a regular expression
• is a regular expression
• is a regular expression
• if r and s are regular expressions, then so is (r|s)
• if r and s are regular expressions, then so is rs
• if r is a regular expression, then so is (r)

Every regular expression is built up inductively, by finitely many
applications of the above rules.
(N.B. we assume , , (, ), |, and
are not symbols in .)