questions by testbook mock test

Question

Comments

Not able to view question

Answer 1

Statement (1) is well known as right invariance and statement (2) is known as left invariance..

Now as far as extended transition function is concerned , right invariance holds but not left invariance..

We can think about the same intuitively..

Let we start from start state q₀....Now on reading string 'x' and hence applying multiple transition δ*(q₀ , x) we reach say state q_i...Now given  δ*(q₀ , x)  =   δ*(q₀ , y)..

So on reading y also we will reach the same state q_i....

Hence  δ*(q₀ , xz)  means reading string 'z' after string 'x' will lead to same state as δ*(q₀ , yz) as before reading 'z' string in both cases we were in q_i state hence the destination state will also be the same.

Hence right invariance holds..

On the other hand ,

for δ*(q₀ , zx) and δ*(q₀ , zy) , say on reading string 'z' , we reach q_i  ..After that we read 'x' string for first extended transition function and 'y' string for second one..

Now from q_i , on reading 'x' and 'y' we may go to different states..[ As q_i is distinct from q₀ ]

So even though δ*(q₀ , x)  =   δ*(q₀ , y) ,

but  δ*(q₀ , zx)  =   δ*(q₀ , zy) need not hold...

Hence left invariance does not hold here..

Hence option A) should be correct answer..