- Submission Guideline: Upload your homework file (
hw6_[your student id].doc
,hw6_[your student id].hwp
orhw6_[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, Friday, October 28
Please feel free to leave your questions about homework problems in the online Piazza classroom.
- 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.
- 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$.
- For the grammar and each of the strings in Problem 2, give parse trees.
- 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.
- 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.