Morphology Hands-on

Morphology Hands-on

by Ana-Arina Raileanu -
Number of replies: 4
Hello,

I did not fully understand the solution for question IV of the morphology hands-on.
In particular, what is the reasoning behind the following answer?

  • Let ⊗ and ◦ respectively denote cross-product of languages and composition of transducers; and
  • let A, B, C and D be four different non empty regular languages such that A and B have no
  • intersection (A ∩ B = ∅) and A is included in C (A ⊂ C).

The following answer is picked as being correct:
  • (A ⊗ B)+ is included in A + ⊗B+

I am not sure what the result of (A ⊗ B)+
If A is a+ and B is b+, what would (A ⊗ B)+ be?
In reply to Ana-Arina Raileanu

Re: Morphology Hands-on

by Jean-Cédric Chappelier -
Let's start a bit simpler than your question: assume A is a|xx and B is b|yyy
Thus A represents the set { a, xx } and B, the set { b, yyy }.
Then A ⊗ B represents { (a, b), (a, yyy), (xx, b), (xx, yyy) }.
And thus (A ⊗ B)+ is { (a, b), (a, yyy), (xx, b), (xx, yyy), (aa, bb), (aa, byy), (axx, bb), (axx, byyy), (axx, byyy), (axx, yyyyyy), (xxxx, byyy), (aaa,bbb), .... }
all the possible concatenations of elements of A ⊗ B,
with the trivial mapping of "sequences of couples" to "couples of sequences" : (i,u)(j,v) corresponds to (ij, uv).
Formally (A ⊗ B)+ is the set { (r^n, s^n) } with the SAME n, for all possible r in A and s in B (and for all n >= 1).

With the same above example, A+ is { a, xx, aa, axx, xxxx, aaa, aaxx, ...}
and B+ is { b, yyy, bb, byyy, yyyb, yyyyyy, bbb, bbyyy, ....}
and A + ⊗B+ is the cross product of these two sets : { (a,b), (a,yyy), (a,bb), (a, byyy), (a, yyyb), (a, yyyyyy), (a, bbb), (a, bbyyy), (a, ....), ..., (xx, b), (xx, yyy), ... }
Formally, A + ⊗B+ is the set { (r^n, s^m) } for all possible r in A and s in B (and for all n >= 1 and m >= 1), notice that here m is not necessarily equal to n.

Now, in your question, you included "+" in A and B already. This does not change the answer but makes it more complex to write and understand I guess since A and B are no longer finite as in the above simpler example. But the formal answer is the same.

Makes sense ?
In reply to Jean-Cédric Chappelier

Re: Morphology Hands-on

by Jamie Nadi Nessim Mickaill -
Hi there, thanks for the explanation. if (A ⊗ B)+ is the set { (r^n, s^n) } with the SAME n, then how do we express the set {(r,s)^n} e.g. abab for n=2 ?
In reply to Jean-Cédric Chappelier

Re: Morphology Hands-on

by Ana-Arina Raileanu -
Yes, this cleared my confusion. Thank you!
In reply to Ana-Arina Raileanu

Re: Morphology Hands-on

by Jean-Cédric Chappelier -
Let me answer anyway, just in case:

1. first of all, "abab" does not make much sense since I don't see couples;
write it, either (a,b)(a,b) or (aa,bb) or aa:bb (all these are equivalent writings of the same thing)

2. this would simply be described by (A ⊗ B)(A ⊗ B)
(exactly two times); or maybe (A ⊗ B)^2 or (A ⊗ B){2}, with more exotic regexp writings (not presented in class)

3. don't misunderstand "{ (r^n, s^n) } with the SAME n", this is for ALL n (and not for a given single n; but for any n, this n is the same for r and s); makes sense?
(i updated my answer above to clarify further this later point)