regular languages

Question

let ∑ = {0, 1, +, =} and
L = { x=y+z | x, y, z are binary integers, and x is the sum of y and z }. Is L regular ?

Answer 1

As far as y and z is concerned , we have no problem as they can be any binary string..But as far as z is concerned , it is given that it should be binary sum of y and z ..Then only the string :

x  =  y + z

is accepted by the language else not..So for that we need to have addition capability of the machine so that we can find out about whether x is equal to sum of y and z or not..

Then the given language reduces to :

L  =  { x = x | x is a binary string } which we know very well that it is a CSL and hence not regular..

So it is clear that the given language is not regular..

To know about whether it is CSL or not , we see that here addition of y and z needs to be performed which cannot be done by a linearly bounded automata but can be done by a Turing Machine..

Hence the given language is not CSL as well.. 

Comments

@ Habib sir , in the above solution there is a misprint in the following line--

---

@Habib , thank you sir , for making my concept clear.