Constructing regular expressions with given substring requirments - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-07-17T06:51:58Z https://cs.stackexchange.com/feeds/question/14568 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/14568 1 Constructing regular expressions with given substring requirments Paul Spinelli https://cs.stackexchange.com/users/10190 2013-09-24T01:20:20Z 2013-09-24T02:21:21Z <p>I'm having trouble with this question about regular expressions:</p> <blockquote> <p>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$.</p> </blockquote> <p>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*}</p> <p>I'm really stuck on this second part:</p> <blockquote> <p>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?</p> </blockquote> <p>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.</p> https://cs.stackexchange.com/questions/14568/-/14569#14569 1 Answer by Yuval Filmus for Constructing regular expressions with given substring requirments Yuval Filmus https://cs.stackexchange.com/users/683 2013-09-24T02:21:21Z 2013-09-24T02:21:21Z <p>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$.</p> <p>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 <em>intersect</em> regular expressions (do you see how that helps?).</p>