Syntaxuppgifter från omtentan 12 juni 2012 1. Strängkonstanter i programspråket Pascal definieras på följande sätt: En strängkonstant består av strängen omgiven av apostrofer, till exempel 'Detta är en sträng.' Om man vill ha en apostrof inuti en sträng skriver man två apostrofer efter varandra: 'Go''dag, sa'' gubben.' är strängen Go'dag sa' gubben. Ge ett reguljärt uttryck som beskriver sådana strängkonstanter. Anta att strängarna bara kan innehålla svenska bokstäver, siffror, blanksteg och apostrofer. a) '[A-ZÅÄÖa-zåäö0-9 '']*' b) '([A-ZÅÄÖa-zåäö0-9 ]|'')*' c) '([A-ZÅÄÖa-zåäö0-9 ]+|'')*' d) '([A-Z]|[a-z]|[åäöÅÄÖ]|[0-9]| |'')*' e) inget av ovanstående 2. Kan språket {vwv: v och w är strängar över alfabetet {a,b} och längden av v är 2} beskrivas med ett reguljärt uttryck? a) Nej b) Ja, nämligen aa[ab]*aa|ab[ab]*ab|ba[ab]*ba|bb[ab]*bb c) Ja, nämligen v(a|b)*v d) Ja, nämligen [ab][ab][ab]*[ab][ab] e) Ja, men inget av ovanstående reguljära uttryck 3. Rangordna beräkningsmodellerna PDA, NFA, DFA med avseende på hur komplicerade språk dom kan känna igen. Tala också om ifall några beräkningsmodeller är lika kraftfulla. a) NFA=PDA