Transcript Key answers for homework #2 ()

Key to Homework #2
1. What is the language of L-system G = ({a, b, c}, h, acb ), where the rewriting rule h is defined as follows:
h (a) = aa h (b) = cb h (c) = a
Answer: Applying h iteratively on acb, we get the following: acb  aaacb  aaaaaaacb  aaaaaaaaaaaaaaacb  . . .
The number of a’s increases with the following pattern; 1, 2+1, 4+2+1, 8+4+2+1, . . . , and so on. If we apply h i times, we get
string a1a2a4. . . .aicb. Since 1+2+4+8+ . . . +2i = 2i+1 – 1, we can express the language of the L-system as follows.
{ arcd | r = 2i+1 – 1, i  0 }
2. Construct a syntax diagram which defines the language of the following context-free grammar.
S  aSbB | A A  bSa | ba | ab
B  bB | 
Answer:
S
A
a
S
A
b
B
B
b
S
a
b
a
b
B
4. Suppose that in the Pascal Syntax Flow Graph (see your handout) digit are defined as the following syntax flow graphs.
Write a context-free grammar that generates all unsigned numbers defined by the Pascal syntax flow graph “unsigned
number” in the handout.
digit
1
We use lower case letter instead
of capital E, to show that it is
terminal symbol.
2
unsigned number
+
unsigned integer
.
digit
e
-
Answer:
We know that
unsigned integer
For convenience, define
unsigned integer
sign
+
digit
* Let < . . .> denote nonterminals, and <unsigned number> be the start symbol of the grammar.
.
<unsigned number>  <unsigned integer> <unsigned integer> e <sign> <unsigned integer> |
.
<unsigned integer> <unsigned integer> | <unsigned integer> e <sign> <unsigned integer> | <unsigned integer>
<unsigned integer>  <digit> | <unsigned integer> <digit>
<digit>  1 | 2
<sign>  + | - | 
3. What does the following Turing Machine (TM) do? Explain in detail referring to the states. Assume that
the input is a string in { 0, 1 }+. (Hint: Trace the machine operation with a simple example.)
(0,0,L)
(1,1,R)
(0,0,R)
start
(1,0,L)
0
4
(0,B,L)
(1,1,R)
(0,0,R)
(B,0,N)
(B,B,L)
1
2
(B,B,L)
(0,1,L)
3
6
(1,0,L)
(0,1,R)
(1,B,L)
5
(B,1,N)
Answer:
Given a binary number on the tape, the Turing machine increments and shifts
it as follows:
(1)
(2)
•
(3)
(4)
(1,1,L)
In state 0, the head move all the way to the right until it the blank next to the last symbol, and back up one cell to the
left and enters state 1.
Moving to the left changes all 1’s to 0, until it reads 0. The machine changes this 0 to 1, enters state 2 and moves all
the way to the right until it hits a blank, and then back up in state 3.
Above procedures (1) and (2) increment the binary number on the tape by one. (There is an exceptional case; if the
number is all 1’s, the increment will be stuck at state 1, and will not work.)
If the machine reads symbol 0 (symbol 1), it replaces the symbol with blank and moves to the left entering state 4
(respectively, state 5).
Changing states between 4 and 5, the machine shifts the binary string to the left by one cell.
5. Construct a TM which, given a string x  {a, b}+, rearrange the symbols in x such that all a’s come fist then b’s follow.
For example, if the input is abbaaba, then the result will be aaaabbb. When the work is complete the TM should be in an
accepting state and the tape should only contain rearranged string. For your answer, you should first informally explain
your idea in detail and then show the transition graph of the TM.
An idea: Shifting the input string to the right, if there is a symbol b before an a, stop shifting and move that b to
the end of the string. This operation repeats until it sees no b to the left of an a.(See the illustration in Figure (a).)
In Figure (b), the machine enters in state 3 if it sees an a after reading b’s.
Go for next iteration.
Put b at the end.
(a, a, L),
(b, b, L)
aababbaab
(a, a, R),
(b, b, R)
(B, b, L)
4
aaabbaabb
This is an a out of order
3
(B, B, R)
aaabaabbb
(b, B, R)
aaaaabbbb
start
(a, a, R)
5
0
(B, b, N)
aaaaabbbb
2
(a, B, R)
accept
1
(b, a, R)
(b, b, R)
(a, a, R)
(B, a, N)
Figure (a). Shifting the string and transposing b’s.
Figure (b). State transition graph