Let's solve each part step-by-step: --- ### (a) Write a regular expression for passwords with: - At least one digit - Only letters and digits - No spaces or special characters. #### **Solution:** Let: - `D` = `[0-9]` (digits) - `A` = `[A-Za-z]` (letters) - `S` = `[A-Za-z0-9]` (letters and digits) We need at least one digit **anywhere** in the string, and only letters/digits. A common trick is to use: `S* D S*` But this only matches strings with exactly one digit. For at least one digit, we need to allow for any number of letters/digits before and after at least one digit. **General Regular Expression:** ``` ([A-Za-z0-9]*[0-9][A-Za-z0-9]*)+ ``` **Explanation:** - `[A-Za-z0-9]*` — zero or more letters/digits before the digit - `[0-9]` — at least one digit must appear - `[A-Za-z0-9]*` — zero or more letters/digits after the digit - The `+` ensures at least one such segment (at least one digit). --- ### (b) Describe a regular language where all strings contain "101" but never contain "111". #### **Solution:** **Language Description:** Strings over `{0,1}` such that every string contains the substring "101" **at least once** and **never** contains the substring "111". **Regular Expression:** ``` (0|10|110)*101(0|10|110)* ``` **Explanation:** - `(0|10|110)*` — any sequence of 0, 10, or 110 (none of which end in "11") - `101` — required substring - `(0|10|110)*` — any sequence after "101" avoiding "111" This ensures "101" appears at least once, and "111" never appears. --- ### (c) Prove using the Pumping Lemma that the language \( L = \{a^p \mid p \text{ is a prime number}\} \) is not regular. #### **Solution:** **Pumping Lemma Statement:** If \( L \) is regular, there exists a pumping length \( p \) such that any string \( s \) in \( L \) with \( |s| \geq p \) can be written as \( s = xyz \), where - \( |xy| \leq p \) - \( |y| > 0 \) - \( xy^iz \in L \) for all \( i \geq 0 \) **Proof:** - Let the pumping length be \( p \). - Choose \( s = a^q \), where \( q \) is a prime and \( q \geq p \). - Split \( s = xyz \) where \( y = a^k \), \( k > 0 \). - If we pump \( y \) (i.e., repeat it \( i \) times), the length becomes \( q + (i-1)k \). - For \( i = 2 \), length is \( q + k \). - For \( i = 3 \), length is \( q + 2k \). But \( k \) divides the difference, so for some \( i \), \( q + (i-1)k \) is **not prime** (since it can be made composite by choosing \( i \) such that \( q + (i-1)k \) is divisible by \( k \)), so the resulting string is not in \( L \). **Therefore,** the language is **not regular**. --- ### (d) Provide an example of a string that belongs to the language generated by the context-free grammar G1, but not to the language generated by the context-free grammar G2, where G1 and G2 differ in their production rules for recursive structures. #### **Solution:** Suppose: - **G1**: \( S \rightarrow aSa \mid bSb \mid \epsilon \) (generates even-length palindromes) - **G2**: \( S \rightarrow aSb \mid bSa \mid \epsilon \) (generates strings with equal number of a's and b's in mirrored positions) **Example string:** `"abba"` - `"abba"` is a palindrome (belongs to G1). - In G2, the only strings generated are those where the first and last letters are different (like "abab", "baba", etc.), so "abba" **cannot** be generated by G2. **Therefore:** - `"abba"` ∈ L(G1) but `"abba"` ∉ L(G2) --- ## **Summary of Answers:** **(a)** `([A-Za-z0-9]*[0-9][A-Za-z0-9]*)+` **(b)** Regular language: Strings over `{0,1}` containing "101" but never "111". Regex: `(0|10|110)*101(0|10|110)*` **(c)** Not regular by Pumping Lemma — pumping produces non-prime lengths. **(d)** Example: `"abba"` is generated by G1 (palindrome grammar) but not by G2 (alternating letters grammar).