Setul 10

1. Se dau următoarele premise:

• • Orice elev e fericit dacă toți prietenii săi reușesc bacalaureatul.

  • Orice elev bun își ajută prietenii.

  • Oricine e ajutat de cineva reușește tot ce încearcă.

  • Orice elev încearcă bacalaureatul.

și concluzia: Orice elev bun e fericit.

• 1. Formalizați afirmațiile de mai sus.

  2. Găsiți o interpretare (un exemplu de univers, împreună cu valorile predicatelor) în care premisele sunt adevărate, dar concluzia nu.

  3. Demonstrați că premisele implică concluzia într-un univers format doar din elevi.

  4. (Împreună cu punctul anterior, asta ne arată că nu e corect să formalizăm problema fără predicatul 'elev', presupunând implicit că orice X e elev).

  5. Modificați una din premise astfel încât concluzia să devină adevărată (fără vreo altă restricție).

2. Definiți (desenați) un automat care acceptă toate șirurile de 0 și 1 care nu au trei simboluri identice consecutive.

Indicatie: Automatul va avea stări care corespund ultimelor două simboluri întâlnite (sau altfel zis, indică numărul de simboluri identice de la sfârșitul șirului parcurs, și de care fel: 1100100 are la sfârșit două simboluri 0; 1101 are la sfârșit un simbol 1).

3. Pentru expresia regulată de la curs: (0|10)^*(1|ε):

a) scrieți toate șirurile de lungime 5 pe care le generează (adică din limbajul descris de expresia regulată)

b) demonstrați cât mai riguros că ea generează orice șir de 0 și 1 care nu are două simboluri 1 consecutive.