Ćwiczenia 09: Gramatyki (1)

Na ćwiczeniach nr 9 zaczynamy zadania z gramatyk. Podaj gramatykę generującą

  1. Wszystkie słowa w \( \in {a,b}*\) t. że #(a,w)<>#(b,w)
  2. Wszystkie słowa w \(\in {a,b}* \)poza abababb .
  3. Języki typu \(a^n b^k c^m\) takie, że n,k,m spełniają jakieś
    równania/nierówności liniowe np

    • n+k=m
    • n+m=k
    • n+m=k+1
    • n+m<>k
    • n+2m=k+2
      itp.
  4. Język nawiasów kwadratowych i okrągłych; kwadratowych nie można umieszczać wewnątrz okrągłych.
  5. Wyrażenia boolowskie