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

De descripcions informals a formals

Donat un alfabet \Sigma, sovint es poden descriure llenguatges interessants L\subseteq \Sigma^* utilitzant la notació de conjunts L=\{w\in \Sigma^* \mid P(w)\}, on P(w) és un predicat (P) definit sobre un mot w. Per exemple, el llenguatge L de tots els mots sobre \{a,b\} que contenen el submot ab es pot descriure com

L=\{w\in \{a,b\}^* \mid \exists x,y\in \{a,b\}^*\ w=xaby\}.

Descriviu els llenguatges formal sobre \Sigma=\{a,b\} per les descripcions informals següents de P(w):

  1. A la dreta de cada submot ab de w hi ha algun submot ba.
  2. El mot w conté el submot ab i el submot ba.
  3. Entre cada dues b’s hi ha alguna a.
  4. Tota ocurrència de b és en posició parella (el primer símbol d’un mot ocupa la posició 1).
  5. El mot w té algun prefix amb almenys tantes b’s com a’s.
  6. En cada prefix de w hi ha almenys tantes b’s com a’s.
  7. El mot w té algun prefix de mida parella amb almenys tantes b’s com a’s.
  8. Tot prefix de w de mida parella té almenys tantes b’s com a’s.
  9. El mot w té un prefix i un sufix idèntics i no buits de mida més petita que la del mateix mot.
  10. El mot w és un palíndrom, és a dir, es llegeix igual d’esquerra a dreta com de dreta a esquerra, com ara tot o anilina en català.

Per definir la propietat P(w) formalment, feu servir quantificadors universals i existencials (\forall, \exists), operadors Booleans (\lor, \land, \implies, …) i les notacions sobre mides de mots intruduïdes a classe.