Logikk, induktiv definisjon av språk

[kaaasen]

Hei igjen.

 

Har fått god hjelp her tidligere, så jeg prøver meg igjen. Jeg har fått tre oppgaver jeg sliter med. Eller, dvs, jeg tror oppgave b er løst på en grei måte, men jeg ser ikke hvordan jeg skal finne riktig løsning på a og c.

 

All hjelp settes umåtelig stor pris.

 

 

a) Gi en induktiv definisjon av språket {an, bn | n = 0, 1, 2, …}, det vil si {λ, a, b, aa, bb, aaa, bbb, …}.

SVAR: Definert induktivt: Den minste mengden S er slik at x ∈ S, så axb ∈ S.

Hvis x ∈ S, ax ∈ S og bx ∈ S.

KONKATENERING: x konkatenert med a, setter betingelsen på at det slutter på a.

 

b) Gi en induktiv definisjon av språket {an bn | n = 0, 1, 2, …}, det vil si {λ, ab, aabb, aaabbb, …}.

SVAR: Basismengden er λ. Hvis x ∈ S, axb ∈ S.

 

 

c) Gi en induktiv definisjon av språket {(ab)n | n = 0, 1, 2, …}, det vil si {λ, ab, abab, ababab,…}.

SVAR: Basismengden er λ. Hvis x ∈ S, xab ∈ S.