1
$\begingroup$

I'm having trouble with this question about regular expressions:

Let $L_1$ be the language of passwords containing at least one lowercase letter, at least one uppercase letter, and at least one number. Write down a regular expression that describes $L_1$.

This is my answer, but I'm not too sure about it. I let $\mathcal{A}$ be the alphabet, and attempted to cover all permutations. I think my answer is correct, but is there a simpler way to go about it? \begin{equation*} (\mathcal{A}^*\mathcal{A}_{LC}\mathcal{A}^*\mathcal{A}_{UC}\mathcal{A}^*\mathcal{A}_{No}\mathcal{A}^*) \cup (\mathcal{A}^*\mathcal{A}_{LC}\mathcal{A}^*\mathcal{A}_{No}\mathcal{A}^*\mathcal{A}_{UC}\mathcal{A}^*) \cup (\mathcal{A}^*\mathcal{A}_{No}\mathcal{A}^*\mathcal{A}_{LC}\mathcal{A}^*\mathcal{A}_{UC}\mathcal{A}^*) \cup (\mathcal{A}^*\mathcal{A}_{No}\mathcal{A}^*\mathcal{A}_{UC}\mathcal{A}^*\mathcal{A}_{LC}\mathcal{A}^*) \cup (\mathcal{A}^*\mathcal{A}_{UC}\mathcal{A}^*\mathcal{A}_{LC}\mathcal{A}^*\mathcal{A}_{No}\mathcal{A}^*)\cup (\mathcal{A}^*\mathcal{A}_{UC}\mathcal{A}^*\mathcal{A}_{No}\mathcal{A}^*\mathcal{A}_{LC}\mathcal{A}^*) \end{equation*}

I'm really stuck on this second part:

Let $L_2$ be the language of "good" password. It is related to L1 by: \begin{equation*} L_2=\{w\in L_1 : w \text{ has length } \geq 8\} \end{equation*} Specify a regular expression that describes $L_2$, without writing it down in full. What is the length of this regex?

I'm not sure about how to construct a regular expression using my answer for $L_1$. I thought it might be similar to the first part, where I could specify all the permutations.

$\endgroup$
1
$\begingroup$

Hint: Replace each sub-expression of the form $\Sigma^* A \Sigma^* B \Sigma^* C \Sigma^*$ with a union of expressions of the form $\Sigma^\alpha \Sigma^* A \Sigma^\beta \Sigma^* B \Sigma^\gamma \Sigma^* C \Sigma^d \Sigma^*$ for appropriate $\alpha,\beta,\gamma,\delta$.

Notice also the point of the exercise, namely that (plain) regular expressions aren't a good fit for describing passwords. We would really appreciate being able to intersect regular expressions (do you see how that helps?).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.