Formal Language and Automata Homework 6

   

  • Submission Guideline: Upload your homework file (hw6_[your student id].doc, hw6_[your student id].hwp or hw6_[your student id].pdf) to online Eruri classroom. You are allowed to write down your answers either in Korean or English at your convenience.
  • Deadline : 18:00 PM, Tuesday, October 19

       

Please feel free to leave your questions about homework problems in the online Eruri 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.