T Naughton, NUIM
Back to SE307 home

Lab 5 - Machines simulating machines (finite automata)

Use the guidelines from the previous lab when answering problems that refer to finite automata being embedded in TMs.

Note: Where S={0,1}, we can replace the regular expression (1È0) with the more compact regular expression S. Therefore, we could write SS to mean (1È0)(1È0) (i.e. all words over S of length exactly two).

Note: As always, the term FA implies DFA.

Machine 5.1 Construct a FA, embedded in a TM, that accepts the language defined by the regular expression (1È0)0*.

Machine 5.2 Let S={0,1,2}. Construct a FA, embedded in a TM, that accepts the language defined by the regular expression S(0È11È12)*S*.

Machine 5.3 Let S={a,b}. Construct a FA, embedded in a TM, that accepts the language defined by the regular expression eÈSÈ(aS*a)È(bS*b).

Machine 5.4 Let S={0,1}. Construct a FA, embedded in a TM, that accepts the language defined by the regular expression ÆÈeÈSÈSS.

Machine 5.5 Construct a TM that accepts the language L of FA descriptions of the form (Q,S,d,q₀,F). To make things easier, we will replace the transition function by the symbol D, the possible states will come from the set Q={0,1,2,3}, the possible alphabet symbols will come from the set S={a,b,c}, we will remove parentheses and curly braces, and commas will be replaced by the # symbol. So, each word in L will have the form: a list of states for this FA, followed by #, followed by a list of symbols for this FA, followed by #D#, followed by one state from the list of states for this FA, followed by #, followed by a subset of the states for this FA. All finite automata will contain at least one state in their list, and will have an alphabet of at least one symbol, but may have zero accepting states. For example, the TM should accept 013#bc#D#0#03 and 0#a#D#0#, but should not accept 01#bc#D#0#03 or 013#bc#D#2#03. It is OK for your TM to crash if it receives any badly formatted input word, as long as it does not halt in an accepting state.