Show that NWAs (over nite words) are closed under concatenation.

Careful: The rst nested-word might have unmatched calls and sim-

ilarly the second NWA might have unmatched returns. Make sure they

match properly.

Important: Specify in your construction what are the input and output

NWAs. I don't require a proof of correctness, but clearly state the invariants

maintained by your construction (e.g., after reading the nested word a1:::

the NWA C is in state q with stack p1 : : : pn i ...).

Important: There are two denitions of this model that are equivalent:

Nested Word Automata and Visibly Pushdown Automata. This latter one

might be easier to deal with for this particular problem.