The Gateway to Computer Science Excellence
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.$
in Theory of Computation by Veteran (59.3k points) | 21 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,384 answers
105,330 users