Theory of Computation Homework 2

   

  • Submission Guideline: Upload your homework file (hw2_[your student id].doc or hw2_[your student id].hwp) to online Uclass classroom. You are allowed to write down your answers either in Korean or English at your convenience.
  • Deadline: 23:59 PM, Wednesday, June 5

       

Please feel free to leave your questions about homework problems in the online Uclass classroom.

   

  1. Design context-free grammars for the following languages.

(a) The set of all strings of $a$’s and $b$’s that are not of the form $ww$, that is, not equal to any string repeated.

(b) The set of all strings with twice as many $0$’s as $1$’s.

   

  1. The following grammar generates the language of regular expression $0^* 1(0+1)^* $ :

$S \rightarrow A1B$

$A \rightarrow 0A \mid \epsilon$

$B \rightarrow 0B\mid 1B\mid \epsilon$

Give leftmost and rightmost derivations of the following strings:

(a) $00101$.

(b) $1001$.

(c) $00011$.

   

  1. For the grammar and each of the strings in Problem 2, give parse trees.

   

  1. Consider the set of all strings of balanced parentheses of two types, round and square. An example of where these strings come from is as follows: $f(a[i]*(b[i][j],c[g(x)]),d[i])$. It becomes the balanced-parenthesis string $([\; ]([\; ] [\; ][ () ])[\; ])$.

Design a grammar for all and only the strings of round and square parenthesis that are balanced.

   

  1. Consider the grammar $S \rightarrow aS\mid aSbS\mid \epsilon$.

This grammar is ambiguous. Show in particular that the string $aab$ has two:

(a) Parse trees.

(b) Leftmost derivations.

(c) Rightmost derivations.

   

  1. Suppose the PDA $P$ =$({\{q,p}\},{\{0,1}\},{\{Z_0,X}\},\delta,q,Z_0,{\{p}\})$ has the following transition function:
  • $\delta(q,0,Z_0) = {\{(q,XZ_0)}\}$.

  • $\delta(q,0,X) = {\{(q,XX)}\}$.

  • $\delta(q,1,X) = {\{(q,X)}\}$.

  • $\delta(q,\epsilon,X) = {\{(p,\epsilon)}\}$.

  • $\delta(p,\epsilon,X) = {\{(p,\epsilon)}\}$.

  • $\delta(p,1,X) = {\{(p,XX)}\}$.

  • $\delta(p,1,Z_0) = {\{(p,\epsilon)}\}$.

Starting from the initial ID $(q,w,Z_0)$, show all the reachable ID’s when the input $w$ is:

a) $01$

b) $0011$

c) $010$

   

  1. Design a PDA to accept each of the following languages. You may accept either by final state or by empty stack, whichever is more convenient.

a) The set of all strings of $0$’s and $1$’s such that no prefix has more $1$’s than $0$’s.

b) The set of all strings of $0$’s and $1$’s with an equal number of $0$’s and $1$’s.

   

  1. Consider the PDA $P$ from Problem 6.

a) Convert $P$ to another PDA $P_1$ that accepts by empty stack the same languages that $P$ accepts by final state; i.e., $N(P_1) = L(P)$.

b) Find a PDA $P_2$ such that $L(P_2) = N(P)$; i.e., $P_2$ accepts by final state what $P$ accepts by empty stack.

   

  1. Convert the grammar

$S \rightarrow 0S1 \mid A$

$A \rightarrow 1A0\mid S\mid \epsilon$

to a PDA that accepts the same language by empty stack.

   

  1. Convert the PDA of Problem 6 to a context-free grammar.