GATE CSE 2020

Question

Is this language a regular language ? If yes why and if No why ?

The last part is “x!=y” cropped in the picture

According to my understanding this is not regular because its says

number of x = number of y

But Finite automata cant compare the number of x and y here with limited memory. Can you please explain ?

Comments

Let x length is i, then y length should be i.

Therefore strings which are present in the language lengths are 2i. That mean even length strings. This can be recognised by FA.

---

This language is non-regular not because $|x| = |y|$, because if language would have been $\{xy \mid |x| = |y| \}$ then language will contain set of all even length strings which can be recognized by DFA.
It is non-regular because $x \neq y$ for which we have to compare substring $x$ and $y$ which we can’t do by DFA

Answer 1

IT IS NOT REGULAR .

As finite automata is memory less model

it have no any memory to know that how much number of x so how it able to compute that must equal to y an in given question its |x| = |y| mean cardinality of x and cardinality of y must same but its not possible