in Theory of Computation
72 views
0 votes
0 votes

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 ?

in Theory of Computation
by
72 views

2 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.
1
1
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
2
2

Please log in or register to answer this question.

Related questions