87 |
87 |
88 |
88 |
89 \begin{document} |
89 \begin{document} |
90 |
90 |
91 \maketitle |
91 \maketitle |
|
92 Suppose (basic) regular expressions are given by the following grammar: |
92 |
93 |
93 Hello. |
94 \[ r ::= \ZERO \mid \ONE |
94 Let us play with the function $f$ on annotated regular expressions: |
95 \mid c |
|
96 \mid r_1 \cdot r_2 |
|
97 \mid r_1 + r_2 |
|
98 \mid r^* |
|
99 \] |
|
100 |
|
101 |
|
102 If we let the alphabet |
|
103 where $c$ is selected from |
|
104 be $\sum = \{0,1\}$, |
|
105 then bitcodes can be defined in a |
|
106 regular expression style: |
|
107 |
|
108 |
|
109 \[ bs ::= \ZERO \mid \ONE |
|
110 \mid 1 |
|
111 \mid 0 |
|
112 \mid bs_1 \cdot bs_2 |
|
113 \mid \sum{bs_{list}} |
|
114 \mid bs^* |
|
115 \] |
|
116 |
|
117 We can define an isomorphism between the regex |
|
118 definition of bitcodes and our list definition of bitcodes: |
95 \begin{center} |
119 \begin{center} |
96 $f(\ZERO) = \ZERO$ |
120 $b ::= 1 \mid 0 \qquad |
|
121 bs ::= [] \mid b::bs |
|
122 $ |
|
123 \end{center} |
|
124 For example we can let $\sigma([])= \ONE$. |
|
125 But how to define such isomorphism in detail is not explicitly needed for now. |
|
126 |
|
127 \emph{Annotated regular expressions} can be defined by the following |
|
128 grammar using new $bs$ definition: |
|
129 |
|
130 \begin{center} |
|
131 \begin{tabular}{lcl} |
|
132 $\textit{a}$ & $::=$ & $\ZERO$\\ |
|
133 & $\mid$ & $_{bs}\ONE$\\ |
|
134 & $\mid$ & $_{bs}{\bf c}$\\ |
|
135 & $\mid$ & $_{bs}\sum\,as$\\ |
|
136 & $\mid$ & $_{bs}a_1\cdot a_2$\\ |
|
137 & $\mid$ & $_{bs}a^*$ |
|
138 \end{tabular} |
|
139 \end{center} |
|
140 Let the set of all bitcoded regular expressions be $\textit{BS}$. |
|
141 Let the set of all annotated regular expression be $\textit{AR}$. |
|
142 Let us play with the function $f: \textit{AR} \rightarrow \textit{BS}$ on annotated regular expressions: |
|
143 \begin{center} |
|
144 $f(\ZERO) = \ZERO$\\ |
97 $f(_{bs}\ONE) = \textit{bs}$\\ |
145 $f(_{bs}\ONE) = \textit{bs}$\\ |
98 $f(_{bs}a) = \textit{bs} $\\ |
146 $f(_{bs}a) = \textit{bs} $\\ |
99 $f(_{bs}r_1\cdot r_2) = \textit{bs} \cdot $ |
147 $f(_{bs}r_1\cdot r_2) = \textit{bs} \cdot( f(r_1) \cdot f(r_2))$\\ |
100 $f(_{bs}\sum{rs}) = \textit{bs} \cdot \sum\limits_{r \in rs}{f(\textit{r})}$\\ |
148 $f(_{bs}\sum{rs}) = \textit{bs} \cdot \sum\limits_{r \in rs}{f(\textit{r})}$\\ |
101 $f(_{bs}r*) = \textit{bs} \cdot((0 \cdot f(r))\cdot 1) $ |
149 $f(_{bs}r^*) = \textit{bs} \cdot((0 \cdot f(r))^*\cdot 1) $ |
102 \end{center} |
150 \end{center} |
103 |
151 |
|
152 We claim that: |
|
153 \begin{center} |
|
154 $f(a) = \{bs \mid a \gg bs\}$. |
|
155 \end{center} |
104 |
156 |
105 \bibliographystyle{plain} |
157 \bibliographystyle{plain} |
106 \bibliography{root} |
158 \bibliography{root} |
107 |
159 |
108 |
160 |