⟸ pàgina anterior ⟸
Exercici 2 (Tasca 1).
(theory of languages, concatenation)

Concatenació — propietats bàsiques

Justifiqueu les vostres respostes a les preguntes següents. Els mots i els llenguatges corresponen a un alfabet fixat.

  1. És la concatenació commutativa? Es compleix que xy=yx per tots els mots x,y? Es compleix que AB=BA per tots els llenguatges A,B? Depenen les respostes anteriors de la mida de l’alfabet?
  2. És la concatenació de llenguatges associativa? Es compleix que x(yz)=(xy)z per tots els mots x,y,z? Es compleix A(BC)=(AB)C per tots els llenguatges A,B,C? Depenen les respostes anteriors de la mida de l’alfabet?
  3. Es compleix la llei de cancel·lació per la concatenació de mots? És a dir, es compleix que xy=xz implica y=z per tots els mots x,y,z?
  4. Es compleix la llei de cancel·lació per la concatenació de llenguatges? És a dir, es compleix que AB=AC implica B=C per tots els llenguatges A,B,C? I si addicionalment imposem que A\neq \emptyset, es compleix ara?
  5. Condició per una doble igualtat. Donats quatre llenguatges A,B,C,D tals que A,B són no buits, AB=CD i tots els mots a A i C tenen la mateixa mida, es compleix que A=C and B=D?
  6. Distribueix la concatenació de llenguatges sobre la reunió? És a dir, es compleix que (A\cup B) C=AC\cup BC i A(B\cup C)=AB\cup AC per tots els llenguatges A,B,C? I si en lloc de “=” només demanem “\subseteq” o “\supseteq”, es compleix ara?
  7. Distribueix la concatenació de llenguatges sobre la intersecció? És a dir, es compleix que (A\cap B) C=AC\cap BC i A(B\cap C)=AB\cap AC per tots els llenguatges A,B,C? I si en lloc de “=” només demanem “\subseteq” o “\supseteq”, es compleix ara?