edited by
181 views
0 votes
0 votes
Let $w_{1}=a_{0}a_{0}a_{1},$ and $w_{i}=w_{i-1}w_{i-1}a_{i}$ for all $i>1.$For instance,$w_{3}=a_{0}a_{0}a_{1}a_{0}a_{0}a_{1}a_{2}a_{0}a_{0}a_{1}a_{0}a_{0}a_{1}a_{2}a_{3}.$ The shortest regular expression for the language $L_{n}=\{w_{n}\},$ i.e., the language consisting of the one string $w_{n}$ is the string $w_{n}$ itself and the length of this expression is $2^{n+1}-1.$ However if we allow the intersection operator we, can write an expression for $L_{n}$ whose length is $O(n^{2}).$ Find such an expression. Hint $:$ Find $n$ languages, each with regular expressions of length $O(n).$ Whose intersection is $L.$
edited by

Please log in or register to answer this question.

Related questions