Is {xy | x, y ∈ Σ∗ and x contains more a’s than y} regular? I've been asked to write a DFA for:
$\{xy\mid x, y \in \Sigma^*\text{ and }x\text{ contains more }a\text{’s than }y\}$ where $\Sigma=\{a,b\}$.
I don't believe this is possible. Can anyone confirm if this is not a regular language so that I'm not wasting my time if I'm correct.
Edit
Thinking again, while it's impossible to track exactly how many $a$'s are in $x$ or $y$ respectively, we know $x$ must have the number of $a&gt;0$ at the very least and that the number of $a$'s in the string cannot be 2 since the condition of 'more' $a$'s has to be satisfied. Can you just write a DFA accepting strings with inputs containing 1 $a$, and 3+ $a$'s to satisfy the language?
Since the language does not specify what $x$ and $y$ are, you can always let $y=\varepsilon$, i.e., the empty string, then the language only requires $x$ to contain at least 1 $a$. So equivalently, the language is

$\{x\in\Sigma^*\mid x\text{ contains at least 1 }a\}$.

Now it is easy to build a DFA to accept this language.