Ange regulär uttryck! (Matematik/Universitet)

Jag är inte insatt i reguljära uttryck, men eventuellt kan du ha användning av länkarna nedan:

http://fileadmin.cs.lth.se/cs/education/EDAF10/documents/kap6-7.pdf

https://csharpskolan.se/article/reguljara-uttryck/

Hur ser uppgiften ut?

Tack @markusbystrom

@Laguna det är två frågor

1. bevis att alla språk som består ändligt många ord är reguljära.

2. Ange reguljära uttryck för språket som innehåller alla ord som innehåller minst tre a:n och slutar på b:n .

För mig är detta ingen matematikuppgift.
Den hör hemma i systemvetenskap eller lingvistik,
och då närmast datorlingvistik.

Där har jag har träffat på sådant men aldrig i matematik

shavab99 skrev:
Tack @markusbystrom
@Laguna det är två frågor
1. bevis att alla språk som består ändligt många ord är reguljära.
2. Ange reguljära uttryck för språket som innehåller alla ord som innehåller minst tre a:n och slutar på b:n .

Till att börja med är det en fråga per tråd, men...

1. Jag vet inte riktigt hur ett riktigt bevis skulle se ut, det kan du få fnula på själv. Notera dock att om ett språk L är ändligt så är unionen av elementen i L ett reguljärt uttryck för språket.

2. Man kan antagligen snygga till det lite, det var ett tag sedan jag läste en kurs i detta. Men ett reguljärt uttryck som borde fungera är väl typ (underförstått att alfabetet då är a och b):

$b^{*} a {(a \cup b)}^{*} a {(a \cup b)}^{*} a {(a \cup b)}^{*} b^{*}$ .

Hänger du med? Synpunkter? Frågor?

Moffen skrev:
shavab99 skrev:
Tack @markusbystrom
@Laguna det är två frågor
1. bevis att alla språk som består ändligt många ord är reguljära.
2. Ange reguljära uttryck för språket som innehåller alla ord som innehåller minst tre a:n och slutar på b:n .
Till att börja med är det en fråga per tråd, men...
1. Jag vet inte riktigt hur ett riktigt bevis skulle se ut, det kan du få fnula på själv. Notera dock att om ett språk L är ändligt så är unionen av elementen i L ett reguljärt uttryck för språket.
2. Man kan antagligen snygga till det lite, det var ett tag sedan jag läste en kurs i detta. Men ett reguljärt uttryck som borde fungera är väl typ (underförstått att alfabetet då är a och b):
$b^{*} a {(a \cup b)}^{*} a {(a \cup b)}^{*} a {(a \cup b)}^{*} b^{*}$ .
Hänger du med? Synpunkter? Frågor?

Jaha men i fråga två kan man inte istället säga:

.a^*.a^*.a^*.b^*/W

den innehåller tre a:n och slutar på b. Det exemplet du gav vad betyder (aUb) eller med andra ord kan du förklara det du har skrivit med ord. Tacksam för svar.

shavab99 skrev:
Moffen skrev:
shavab99 skrev:
Tack @markusbystrom
@Laguna det är två frågor
1. bevis att alla språk som består ändligt många ord är reguljära.
2. Ange reguljära uttryck för språket som innehåller alla ord som innehåller minst tre a:n och slutar på b:n .
Till att börja med är det en fråga per tråd, men...
1. Jag vet inte riktigt hur ett riktigt bevis skulle se ut, det kan du få fnula på själv. Notera dock att om ett språk L är ändligt så är unionen av elementen i L ett reguljärt uttryck för språket.
2. Man kan antagligen snygga till det lite, det var ett tag sedan jag läste en kurs i detta. Men ett reguljärt uttryck som borde fungera är väl typ (underförstått att alfabetet då är a och b):
$b^{*} a {(a \cup b)}^{*} a {(a \cup b)}^{*} a {(a \cup b)}^{*} b^{*}$ .
Hänger du med? Synpunkter? Frågor?

Jaha men i fråga två kan man inte istället säga:
.a^*.a^*.a^*.b^*/W
den innehåller tre a:n och slutar på b. Det exemplet du gav vad betyder (aUb) eller med andra ord kan du förklara det du har skrivit med ord. Tacksam för svar.

Vad betyder punkten och vad betyder ^ och *?

Moffen skrev:
shavab99 skrev:
Tack @markusbystrom
@Laguna det är två frågor
1. bevis att alla språk som består ändligt många ord är reguljära.
2. Ange reguljära uttryck för språket som innehåller alla ord som innehåller minst tre a:n och slutar på b:n .
Till att börja med är det en fråga per tråd, men...
1. Jag vet inte riktigt hur ett riktigt bevis skulle se ut, det kan du få fnula på själv. Notera dock att om ett språk L är ändligt så är unionen av elementen i L ett reguljärt uttryck för språket.
2. Man kan antagligen snygga till det lite, det var ett tag sedan jag läste en kurs i detta. Men ett reguljärt uttryck som borde fungera är väl typ (underförstått att alfabetet då är a och b):
$b^{*} a {(a \cup b)}^{*} a {(a \cup b)}^{*} a {(a \cup b)}^{*} b^{*}$ .
Hänger du med? Synpunkter? Frågor?

Ska det inte stå b utan stjärna sist? Det här uttrycket kan sluta på a.

Du har rätt Laguna, det där blev lite fel. Å andra sidan ska inte det reguljära uttrycket bara sluta på ett b, men på bb* tror jag. Vi får ju ha hur många b som helst i slutet också, bara det slutar på b.

EDIT: Du har rätt igen, det tas ju hand om i den tidigare parentesen, så jo, den stjärnan ska helt enkelt tas bort.

. betyder att vilken bokstav som helst

* upprepas obegränsat antal gånger

/w vad det slutar eller börjar med

. a*.a*.a*.b*/w

detta bör stämma eller hur? ordet kan börja på vad som helt och innehåller minst 3 a:n och slutar slutligen med ett b.

@moffen kan du förklara hur du gjorde, och varför du gjorde så? gärna med ord. Tacksam för svar :)

Förstår inte riktigt din notation. Betyder " . " att det är vilken bokstav som helst, och hur många gånger får den upprepas?

Jag tänkte typ:

Börja med hur många b:n som vi vill (inklusive 0 st), sen måste vi ha ett a. Efter det kan vi ta vilka kombinationer som helst av a och b (alltså ${(a \cup b)}^{*}$ ), sen återigen måste vi ha ett a. Upprepa tills slutet när vi har 3 a:n, sen kan vi fortsätta hur vi vill, därav ${(a \cup b)}^{*}$ . Men sen måste vi ha ett b eftersom vi måste sluta på b.

Det minsta vi får nu är att välja allt med " * " till inga alls, och får då strängen aaab. Men vi skulle ju kunna välja att ta 3 b i början, och kanske abba i mitten, så typ: bbbaaabbaab.

Gick det att förstå? Men notera att det som jag skrev som du citerade är fel, som Laguna påpekade ska det inte vara en stjärna där på sista b.

shavab99 skrev:
. betyder att vilken bokstav som helst
* upprepas obegränsat antal gånger
/w vad det slutar eller börjar med
. a*.a*.a*.b*/w

detta bör stämma eller hur? ordet kan börja på vad som helt och innehåller minst 3 a:n och slutar slutligen med ett b.
@moffen kan du förklara hur du gjorde, och varför du gjorde så? gärna med ord. Tacksam för svar :)

Som vanligt i reguljära uttryck i programmering, med andra ord, förutom att jag inte förstår /w.

Men a* matchar tomma strängen. * kan innebära inga förekomster alls.

Vi verkar inte vara klara över huruvida det finns andra bokstäver än a och b i språket, dessutom.

jaha du tänkte så men varför tar du unionen? är det ett måste eller valde du bara det?

oj jag råka skriva fel på svaret det ska stå:

.*a.*a.*a.*b/w

dvs ordet kan börja på vad som helst, sen a, sen vad som helst, sen a, sen vad som helst, sen a, sedan vad som helst men måste sluta på b. Ordet innan a får alltså upprepas noll eller obegränsat antal gånger.

shavab99 skrev:
jaha du tänkte så men varför tar du unionen? är det ett måste eller valde du bara det?
oj jag råka skriva fel på svaret det ska stå:
.*a.*a.*a.*b/w
dvs ordet kan börja på vad som helst, sen a, sen vad som helst, sen a, sen vad som helst, sen a, sedan vad som helst men måste sluta på b. Ordet innan a får alltså upprepas noll eller obegränsat antal gånger.

Den notation jag lärt mig och använder är att union i det här sammanhanget innebär att vi kan ta vilken som helst. Med stjärna på det så kan vi bilda vilka ord som helst med a eller b på vilka platser som helst.

Jaha ok så du säger att uttrycket är:

b* a( aUb)* a (aUb)* a (aUb)* b eller hur?

Men får jag fråga dig är mitt exempel rätt också? den senaste du citera? Tacksam för svar!

shavab99 skrev:
Jaha ok så du säger att uttrycket är:
b* a( aUb)* a (aUb)* a (aUb)* b eller hur?
Men får jag fråga dig är mitt exempel rätt också? den senaste du citera? Tacksam för svar!

Ja precis, Laguna rättade mig och mitt exempel ska se ut så där.

Jag ska erkänna att jag fortfarande inte riktigt hänger med i din notation. Som sagt, mitt exempel är fult men det verkar fungera. Ditt exempel fungerar också (om jag förstått det rätt) - men det kan förenklas till mitt exempel genom att bara ersätta ditt första valfria tecken (som kan upprepas hur många gånger som helst? och alla tecken? eller bara tecknet man väljer?) med endast b upprepat valfritt antal gånger. Om du ändå tänker börja med a kan du ju lika gärna köra på från första "måste" a:et.

Jag antar att ditt ".*" är mitt ${(a \cup b)}^{*}$ . Jag föredrar "min" notation, det underlättar och kan på något sätt göra alfabetet mer underförstått (även om det såklart tydligt ska framgå vad vi jobbar med).

Okej, tack så mycket för hjälpen, uppskattar det!

En bra övning kan ju vara att försöka konstruera en DFA för språket också.