equal
deleted
inserted
replaced
67 recognising all strings that do not contain any substring $bb$ and |
67 recognising all strings that do not contain any substring $bb$ and |
68 end in $a$. |
68 end in $a$. |
69 |
69 |
70 \item Do $(a + b)^* \cdot b^+$ and $(a^* \cdot b^+) + (b^*\cdot b^+)$ define |
70 \item Do $(a + b)^* \cdot b^+$ and $(a^* \cdot b^+) + (b^*\cdot b^+)$ define |
71 the same language? |
71 the same language? |
|
72 |
|
73 \item Define the function $zeroable$ by recursion over regular |
|
74 expressions. This function should satisfy the property |
|
75 |
|
76 \[ |
|
77 zeroable(r) \;\;\text{if and only if}\;\;L(r) = \varnothing\qquad(*) |
|
78 \] |
|
79 |
|
80 The function $nullable$ for the not-regular expressions can be defined |
|
81 by |
|
82 |
|
83 \[ |
|
84 nullable(\sim r) \dn \neg(nullable(r)) |
|
85 \] |
|
86 |
|
87 Unfortunately, a similar definition for $zeroable$ does not satisfy |
|
88 the property in $(*)$: |
|
89 |
|
90 \[ |
|
91 zeroable(\sim r) \dn \neg(zeroable(r)) |
|
92 \] |
|
93 |
|
94 Find out why? |
|
95 |
|
96 \item Give a regular expressions that can recognise all strings from the |
|
97 language $\{a^n\;|\;\exists k. n = 3 k + 1 \}$. |
72 \end{enumerate} |
98 \end{enumerate} |
73 |
99 |
74 \end{document} |
100 \end{document} |
75 |
101 |
76 %%% Local Variables: |
102 %%% Local Variables: |