Practise Set

Question

Let L = {automata}   and 

L1=Prefix(L)-ϵ over the alphabet Σ = {0…z},   where Prefix(L) = {x|xy ∈ L, for some y ∈ Σ*} .

Consider a language L₂={x│|x|mod 2 = 0, x ∈ L₁ }
We define half(L) as follows: 
half(L) = {x │∃ y, |x| = |y| and xy ∈ L}
The number of strings in the language half(L₂) is _____.

Answer 1

L={automata}
Prefix(L)={ϵ,a,au,aut,auto,autom,automa,automat,automata}
L₁=Prefix(L)-ϵ={a,au,aut,auto,autom,automa,automat,automata}
L₂ is a language of set of all strings of even length that belongs to L₁.
∴ L₂ = {au,auto,automa,automata}
We define half(L₂) as follows:
half(L₂) = {x│∃y, |x|=|y| and xy∈L₂}
In other words, half(L) consists of the first half of strings in L₂.
half(L₂) = {a,au,aut,auto}
∴ There are 4 strings in half(L₂).

Comments

half(L₂) = {x│∃y, |x|=|y| and xy∈L₂}  equal to half(L) consists of the first halves of strings in L₂.

Can you please explain how ?