Σύστημα-L

Ένα σύστημα-L ή σύστημα Λίντενμαγιερ^[1] είναι ένα παράλληλο σύστημα επανεγγραφής και ένας τύπος τυπικής γραμματικής. Ένα σύστημα-L αποτελείται από ένα αλφάβητο συμβόλων που μπορούν να χρησιμοποιηθούν για να δημιουργήσουν συμβολοσειρές, μια συλλογή κανόνων παραγωγής που αναπτύσσουν κάθε σύμβολο σε κάποια μεγαλύτερη συμβολοσειρά, μια αρχική συμβολοσειρά "αξιωμάτων" από την οποία ξεκινά η κατασκευή, και έναν μηχανισμό για τη μετατροπή των παραγόμενων συμβολοσειρών σε γεωμετρικές δομές. Τα συστήματα-L εισήχθησαν και αναπτύχθηκαν το 1968 από τον Άριστιντ Λίντενμαγιερ, έναν Ούγγρο θεωρητικό βιολόγο και βοτανολόγο του Πανεπιστημίου της Ουτρέχτης^[2] . Ο Λίντενμαγιερ χρησιμοποίησε τα συστήματα-L για να περιγράψει τη συμπεριφορά των φυτικών κυττάρων και να μοντελοποιήσει τις διαδικασίες ανάπτυξης των φυτών. Τα συστήματα-L έχουν επίσης χρησιμοποιηθεί για τη μοντελοποίηση της μορφολογίας διαφόρων οργανισμών^[3] και μπορούν να χρησιμοποιηθούν για τη δημιουργία αυτοομοειδών φράκταλ.

Προέλευση[Επεξεργασία | επεξεργασία κώδικα]

Ως βιολόγος, ο Λίντενμαγιερ εργάστηκε με ζύμες και νηματοειδείς μύκητες και μελέτησε τα πρότυπα ανάπτυξης διαφόρων τύπων βακτηρίων, όπως τα κυανοβακτήρια (Anabaena). Αρχικά, τα συστήματα-L επινοήθηκαν για να παρέχουν μια επίσημη περιγραφή της ανάπτυξης τέτοιων απλών πολυκύτταρων οργανισμών και για να απεικονίσουν τις σχέσεις γειτονίας μεταξύ των φυτικών κυττάρων. Αργότερα, το σύστημα αυτό επεκτάθηκε για να περιγράψει ανώτερα φυτά και πολύπλοκες δομές διακλάδωσης.

Δομή συστήματος-L[Επεξεργασία | επεξεργασία κώδικα]

Η αναδρομική φύση των κανόνων του συστήματος-L^[4] οδηγεί σε αυτοομοιότητα και έτσι οι μορφές που μοιάζουν με φράκταλ είναι εύκολο να περιγραφούν με ένα σύστημα-L. Τα πρότυπα φυτών και οι οργανικές μορφές με φυσική εμφάνιση είναι εύκολο να οριστούν, καθώς με την αύξηση του επιπέδου αναδρομής η μορφή "μεγαλώνει" σιγά-σιγά και γίνεται πιο πολύπλοκη. Τα συστήματα Λίντενμαγιερ είναι επίσης δημοφιλή στη δημιουργία τεχνητής ζωής.

Οι γραμματικές των συστημάτων-L μοιάζουν πολύ με τη γραμματική semi-Thue^[5] (βλ. ιεραρχία του Τσόμσκι). Τα συστήματα-L είναι πλέον ευρέως γνωστά ως παραμετρικά συστήματα-L, τα οποία ορίζονται ως μια πλειάδα

G = (V, ω, P),

Το 'V (το αλφάβητο) είναι ένα σύνολο συμβόλων που περιέχει τόσο στοιχεία που μπορούν να αντικατασταθούν (μεταβλητές) όσο και εκείνα που δεν μπορούν να αντικατασταθούν ("σταθερές" ή "τερματικά").
ω (αρχή, αξίωμα ή εκκινητής) είναι μια σειρά συμβόλων από το V που ορίζει την αρχική κατάσταση του συστήματος.
Το P είναι ένα σύνολο από κανόνες παραγωγής ή παραγωγές που καθορίζουν τον τρόπο με τον οποίο οι μεταβλητές μπορούν να αντικατασταθούν με συνδυασμούς σταθερών και άλλων μεταβλητών. Μια παραγωγή αποτελείται από δύο συμβολοσειρές, τον προκάτοχο και τον διάδοχο. Για κάθε σύμβολο A το οποίο είναι μέλος του συνόλου V που δεν εμφανίζεται στο αριστερό μέρος μιας παραγωγής στο P, θεωρείται η παραγωγή ταυτότητας A → A. Τα σύμβολα αυτά ονομάζονται σταθερές ή τερματικά.

Οι κανόνες της γραμματικής του συστήματος-L εφαρμόζονται επαναληπτικά ξεκινώντας από την αρχική κατάσταση. Εφαρμόζονται ταυτόχρονα όσο το δυνατόν περισσότεροι κανόνες ανά επανάληψη. Το γεγονός ότι σε κάθε επανάληψη εφαρμόζονται όσο το δυνατόν περισσότεροι κανόνες διαφοροποιεί ένα σύστημα-L από μια τυπική γλώσσα που παράγεται από μια τυπική γραμματική, η οποία εφαρμόζει μόνο έναν κανόνα ανά επανάληψη. Αν οι κανόνες παραγωγής εφαρμόζονταν μόνο ένας κάθε φορά, θα μπορούσε κανείς πολύ απλά να παράγει μια συμβολοσειρά σε μια γλώσσα, και όλες αυτές οι ακολουθίες εφαρμογών θα παρήγαγαν τη γλώσσα που καθορίζεται από τη γραμματική. Ωστόσο, υπάρχουν ορισμένες συμβολοσειρές σε ορισμένες γλώσσες που δεν μπορούν να παραχθούν εάν η γραμματική αντιμετωπιστεί ως σύστημα-L και όχι ως γλωσσική προδιαγραφή. Παραδείγματος χάριν,^[6] ας υποθέσουμε ότι υπάρχει ένας κανόνας S→SS σε μια γραμματική. Αν οι παραγωγές γίνονται μία-μία, τότε ξεκινώντας από το S, μπορούμε να πάρουμε πρώτα το SS και μετά, εφαρμόζοντας ξανά τον κανόνα, το SSS. Ωστόσο, αν όλοι οι ισχύοντες κανόνες εφαρμόζονται σε κάθε βήμα, όπως σε ένα σύστημα-L, τότε δεν μπορούμε να πάρουμε αυτή την καταληκτική μορφή. Αντ' αυτού, το πρώτο βήμα θα μας έδινε SS, αλλά το δεύτερο θα εφάρμοζε τον κανόνα δύο φορές, δίνοντάς μας SSSS. Έτσι, το σύνολο των συμβολοσειρών που παράγονται από ένα L-σύστημα από μια δεδομένη γραμματική είναι ένα υποσύνολο της τυπικής γλώσσας που ορίζεται από τη γραμματική, και αν θεωρήσουμε ότι μια γλώσσα ορίζεται ως ένα σύνολο συμβολοσειρών, αυτό σημαίνει ότι ένα δεδομένο L-σύστημα είναι ουσιαστικά ένα υποσύνολο της τυπικής γλώσσας που ορίζεται από τη γραμματική του L-συστήματος.

Ένα σύστημα-L είναι χωρίς περιεχόμενο αν κάθε κανόνας παραγωγής αναφέρεται μόνο σε ένα μεμονωμένο σύμβολο και όχι στα γειτονικά του σύμβολα. Συνεπώς, τα συστήματα-L χωρίς συμφραζόμενα καθορίζονται από μια γραμματική χωρίς συμφραζόμενα. Εάν ένας κανόνας δεν εξαρτάται μόνο από ένα μεμονωμένο σύμβολο αλλά και από τους γείτονές του, ονομάζεται σύστημα-L με συμφραζόμενα.

Εάν υπάρχει ακριβώς μία παραγωγή για κάθε σύμβολο, το σύστημα-L λέγεται προσδιοριστικό (ένα ντετερμινιστικό ελεύθερο συναρτησιακό σύστημα-L ονομάζεται συνήθως σύστημα D0L). Εάν υπάρχουν πολλές και κάθε μία επιλέγεται με ορισμένη πιθανότητα σε κάθε επανάληψη, τότε πρόκειται για ένα στοχαστικό σύστημα-L.

Η χρήση συστημάτων-L για τη δημιουργία γραφικών εικόνων απαιτεί τα σύμβολα του μοντέλου να αναφέρονται σε στοιχεία ενός σχεδίου στην οθόνη του υπολογιστή. Παραδείγματος χάριν, το πρόγραμμα Fractint χρησιμοποιεί γραφικά χελώνας (παρόμοια με αυτά της γλώσσας προγραμματισμού Logo) για να παράγει εικόνες στην οθόνη. Διερμηνεύει κάθε σταθερά σε ένα μοντέλο του συστήματος-L ως εντολή χελώνας.

Παραδείγματα συστημάτων-L[Επεξεργασία | επεξεργασία κώδικα]

Παράδειγμα 1: φύκια[Επεξεργασία | επεξεργασία κώδικα]

Το αρχικό σύστημα-L του Λίντενμαγιερ για τη μοντελοποίηση της ανάπτυξης των φυκών.

μεταβλητές : A B

σταθερές : καμία

αξίωμα : A

κανόνες : (A → AB), (B → A)

που παράγει:

n = 0 : A

n = 1 : AB

n = 2 : ABA

n = 3 : ABAAB

n = 4 : ABAABABA

n = 5 : ABAABABAABAAB

n = 6 : ABAABABAABAABABAABABA

n = 7 : ABAABABAABAABABAABABAABAABABAABAAB

Παράδειγμα 1: φύκια, εξήγηση[Επεξεργασία | επεξεργασία κώδικα]

n=0:               A             έναρξη (αξίωμα/εκκινητής)
                  / \
n=1:             A   B           το μονό Α που προέκυψε στο ΑΒ με (Α → ΑΒ), ο κανόνας (Β → Α) δεν θα εφαρμοζόταν.
                /|     \
n=2:           A B      A        πρώην σειρά ΑΒ με κανόνες που εφαρμόστηκαν, η Α μετατράπηκε σε ΑΒ, η πρώην Β  σε Α
             / | |       | \
n=3:         A B A       A B     Τα Α παράγουν ένα αντίγραφο του εαυτού τους, μετά ένα Β, το οποίο μετατρέπεται ..
           / | | | \     | \ \
n=4:       A B A A B     A B A   ... σε Α μια γενιά αργότερα, αρχίζοντας να γεννά/επαναλαμβάνεται/..

Το αποτέλεσμα είναι η ακολουθία των λέξεων Fibonacci. Αν μετρήσουμε το μήκος κάθε συμβολοσειράς, λαμβάνουμε την περίφημη ακολουθία αριθμών Fibonacci (παραλείποντας το πρώτο 1, λόγω της επιλογής του αξιώματός μας):

1 2 3 5 8 13 21 34 55 89 ...

Αν θέλουμε να μην παραλείψουμε το πρώτο 1, μπορούμε να χρησιμοποιήσουμε το αξίωμα Β. Αυτό θα τοποθετούσε τον κόμβο B πριν από τον κορυφαίο κόμβο (A) του παραπάνω γραφήματος.

Για κάθε συμβολοσειρά, αν μετρήσουμε την k-οστή θέση από το αριστερό άκρο της συμβολοσειράς, η τιμή καθορίζεται από το αν ένα πολλαπλάσιο της χρυσής τομής εμπίπτει στο διάστημα $(k-1,k)$ . Ο λόγος του A προς το B συγκλίνει επίσης στη χρυσή τομή.

Αυτό το παράδειγμα δίνει το ίδιο αποτέλεσμα (όσον αφορά το μήκος κάθε συμβολοσειράς, όχι την ακολουθία των Α και Β) αν ο κανόνας (Α → ΑΒ) αντικατασταθεί με (Α → ΒΑ), με τη διαφορά ότι οι συμβολοσειρές καθρεφτίζονται.

Αυτή η ακολουθία είναι μια τοπικά καθολική ακολουθία επειδή $G(n)=G(n-1)G(n-2)$ , όπου $G(n)$ είναι η n-th γενιά.

Παράδειγμα 2: φράκταλ (δυαδικό) δέντρο[Επεξεργασία | επεξεργασία κώδικα]

μεταβλητές : 0, 1
σταθερές: "[", "]"
αξίωμα : 0
κανόνες : (1 → 11), (0 → 1[0]0)

Το σχήμα κατασκευάζεται με αναδρομική τροφοδότηση του αξιώματος μέσω των κανόνων παραγωγής. Κάθε χαρακτήρας της συμβολοσειράς εισόδου ελέγχεται με βάση τη λίστα κανόνων για να καθοριστεί με ποιον χαρακτήρα ή συμβολοσειρά θα αντικατασταθεί στη συμβολοσειρά εξόδου. Σε αυτό το παράδειγμα, ένα '1' στη συμβολοσειρά εισόδου γίνεται '11' στη συμβολοσειρά εξόδου, ενώ το '[ παραμένει το ίδιο. Εφαρμόζοντας αυτό στο αξίωμα του '0', έχουμε:

αξίωμα:	0
1η αναδρομή:	1[0]0
2η αναδρομή:	11[1[0]0]1[0]0
3η αναδρομή:	1111[11[1[0]0]1[0]0]11[1[0]0]1[0]0
...

Παρατηρούμε ότι αυτή η συμβολοσειρά αυξάνεται ταχύτατα σε μέγεθος και πολυπλοκότητα. Αυτή η συμβολοσειρά μπορεί να σχεδιαστεί ως εικόνα με τη χρήση γραφικά χελώνας, όπου σε κάθε σύμβολο ανατίθεται μια γραφική λειτουργία για να την εκτελέσει η χελώνα. Για παράδειγμα, στο παραπάνω δείγμα, η χελώνα μπορεί να λάβει τις ακόλουθες οδηγίες:

0: σχεδιάστε ένα τμήμα γραμμής που καταλήγει σε ένα φύλλο
1: σχεδιάστε ένα ευθύγραμμο τμήμα
[: θέση push και γωνία, στροφή αριστερά 45 μοίρες
]: θέση pop και γωνία, στροφή δεξιά 45 μοίρες

Τα push και pop αναφέρονται σε μια στοίβα LIFO (μια πιο τεχνική γραμματική θα είχε ξεχωριστά σύμβολα για τα "push position" και "turn left"). Όταν η ερμηνεία της χελώνας συναντήσει ένα '[', η τρέχουσα θέση και γωνία αποθηκεύονται και στη συνέχεια αποκαθίστανται όταν η ερμηνεία συναντήσει ένα ']. Εάν έχουν "σπρώξει" πολλές τιμές, τότε ένα "pop" επαναφέρει τις πιο πρόσφατα αποθηκευμένες τιμές. Εφαρμόζοντας τους γραφικούς κανόνες που αναφέρονται παραπάνω στην προηγούμενη αναδρομή, έχουμε:

αξίωμα

Πρώτη αναδρομή

Δεύτερη αναδρομή

Τρίτη αναδρομή

Τετάρτη αναδρομή

Έβδομη αναδρομή, σε δεκαπλάσια κλίμακα

Παράδειγμα 3: Σύνολο Κάντορ[Επεξεργασία | επεξεργασία κώδικα]

μεταβλητές : A B

σταθερές : χωρίς

έναρξη : A {συμβολοσειρά χαρακτήρων εκκίνησης}

κανόνες : (A → ABA), (B → BBB)

Παράδειγμα 4: Καμπύλη Κοχ[Επεξεργασία | επεξεργασία κώδικα]

Μια παραλλαγή της καμπύλης Κοχ που χρησιμοποιεί μόνο ορθές γωνίες.

μεταβλητές : F

σταθερές : + &minus,

αρχή : F

κανόνες : (F → F+F−F−F+F)

Εδώ, το F σημαίνει "τραβήξτε μπροστά", το + σημαίνει "στρίψτε αριστερά κατά 90°" και το − σημαίνει "στρίψτε δεξιά κατά 90°" (βλέπε γραφικά χελώνας).

n = 0:

F

n = 1:

F+F−F−F+F

n = 2:

F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F

n = 3:

F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F+

F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F−

F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F+

F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F

Είναι επίσης δυνατό να προσεγγίσουμε το τρίγωνο Σιερπίνσκι χρησιμοποιώντας ένα σύστημα-L καμπύλης βέλους Σιερπίνσκι.

μεταβλητές : A B

σταθερές : + &minus,

αρχή : A

κανόνες : (A → B−A−B), (B → A+B+A)

γωνία : 60°

Παράδειγμα 5: Τρίγωνο Σιερπίνσκι[Επεξεργασία | επεξεργασία κώδικα]

Το τρίγωνο Σιερπίνσκι που σχεδιάζεται με τη χρήση συστήματος L.

μεταβλητές : F G

σταθερές : + &minus,

αρχή : F−F−F

κανόνες : (F → F−G+F+G−F), (G → GG)

γωνία : 120°

Εδώ, F σημαίνει "τραβήξτε προς τα εμπρός", G σημαίνει "κινηθείτε προς τα εμπρός", + σημαίνει "στρίψτε αριστερά κατά γωνία" και − σημαίνει "στρίψτε δεξιά κατά γωνία".

n = 2
n = 4
n = 6

Είναι επίσης δυνατό να προσεγγίσουμε το τρίγωνο Σιερπίνσκι χρησιμοποιώντας ένα σύστημα-L καμπύλης βέλους Σιερπίνσκι.

μεταβλητές : A B

σταθερές : + &minus,

αρχή : A

κανόνες : (A → B−A−B), (B → A+B+A)

γωνία : 60°

Εδώ, το Α και το Β σημαίνουν αμφότερα "τραβήξτε προς τα εμπρός", το + σημαίνει "στρίψτε αριστερά κατά γωνία" και το &minus σημαίνει "στρίψτε δεξιά κατά γωνία" (βλέπε γραφικά χελώνας).

Ανάπτυξη προς n = 2, n = 4, n = 6, n = 8

Παράδειγμα 6: καμπύλη δράκου[Επεξεργασία | επεξεργασία κώδικα]

Η καμπύλη του δράκου που σχεδιάζεται με τη χρήση ενός συστήματος L.

μεταβλητές : F G

σταθερές : + -

αρχή : F

κανόνες : (F → F+G), (G → F-G)

γωνία : 90°

Εδώ, το F και το G σημαίνουν αμφότερα "τραβήξτε προς τα εμπρός", το + σημαίνει "στρίψτε αριστερά κατά γωνία" και το - σημαίνει "στρίψτε δεξιά κατά γωνία".

καμπύλη του δράκου για n = 10

Παράδειγμα 7: φυτό φράκταλ[Επεξεργασία | επεξεργασία κώδικα]

Δείτε επίσης τη Φτέρη του Μπάρνσλεϊ

μεταβλητές : X F

σταθερές : + − [ ]

αρχή : X

κανόνες : (X → F+[[X]-X]-F[-FX]+X), (F → FF)

γωνία : 25°

Πρώτα πρέπει να αρχικοποιηθεί μια άδεια στοίβα. Αυτή ακολουθεί τη μέθοδο LIFO (Last in, First Out) για την προσθήκη και αφαίρεση στοιχείων. Στο παρόν παράδειγμα, το F σημαίνει "τραβήξτε προς τα εμπρός", το - σημαίνει "στρίψτε δεξιά κατά 25°" και το + σημαίνει "στρίψτε αριστερά κατά 25°". Το X δεν αντιστοιχεί σε καμία ενέργεια σχεδίασης και χρησιμοποιείται για τον έλεγχο της εξέλιξης της καμπύλης. Η τετράγωνη αγκύλη "[" αντιστοιχεί στην αποθήκευση των τρεχουσών τιμών για τη θέση και τη γωνία, οπότε σπρώχνετε τη θέση και τη γωνία στην κορυφή της στοίβας, όταν συναντήσετε το σύμβολο "]", ανοίγετε τη στοίβα και επαναφέρετε τη θέση και τη γωνία. Κάθε "[" εμφανίζεται πριν από κάθε σύμβολο "]".

Φράκταλ φυτό για n = 6

Παραλλαγές[Επεξεργασία | επεξεργασία κώδικα]

Αναπτύχθηκαν διάφορες παραλλαγές αυτής της βασικής τεχνικής του συστήματος-L, οι οποίες μπορούν να χρησιμοποιηθούν σε συνδυασμό μεταξύ τους. Μεταξύ αυτών είναι οι στοχαστικές γραμματικές, οι γραμματικές που είναι ευαίσθητες στα συμφραζόμενα και οι παραμετρικές γραμματικές.

Στοχαστικές γραμματικές[Επεξεργασία | επεξεργασία κώδικα]

Το μοντέλο γραμματικής που εξετάσαμε μέχρι τώρα ήταν προσδιοριστικό - δηλαδή, δεδομένου οποιουδήποτε συμβόλου στο αλφάβητο της γραμματικής, υπήρχε ακριβώς ένας κανόνας παραγωγής, ο οποίος επιλέγεται πάντα και εκτελεί πάντα την ίδια μετατροπή. Μια εναλλακτική λύση είναι να προσδιορίσουμε περισσότερους από έναν κανόνες παραγωγής για ένα σύμβολο, δίνοντας στον καθένα μια πιθανότητα εμφάνισης. Παραδείγματος χάριν, στη γραμματική του Παραδείγματος 2, θα μπορούσαμε να αλλάξουμε τον κανόνα για την αναγραφή του "0" από:

0 → 1[0]0

σε έναν πιθανό κανόνα:

0 (0.5) → 1[0]0

0 (0.5) → 0

Σύμφωνα με αυτή την επεξεργασία, κάθε φορά που ένα "0" συναντάται κατά την επανεγγραφή συμβολοσειρών, υπάρχει 50% πιθανότητα να συμπεριφέρεται όπως περιγράφηκε προηγουμένως και 50% πιθανότητα να μην αλλάζει κατά την επεξεργασία. Όταν μια στοχαστική γραμματική χρησιμοποιείται σε ένα εξελικτικό πλαίσιο, είναι σκόπιμο να ενσωματώνεται ένας τυχαίος σπόρος στον γονότυπο, έτσι ώστε οι στοχαστικές ιδιότητες της εικόνας να παραμένουν σταθερές μεταξύ των γενεών.

Γραμματικές ευαίσθητες στο περιεχόμενο[Επεξεργασία | επεξεργασία κώδικα]

Ένας κανόνας παραγωγής με ευαισθησία περιβάλλοντος εξετάζει όχι μόνο το σύμβολο που τροποποιεί, αλλά και τα σύμβολα της συμβολοσειράς που εμφανίζονται πριν και μετά από αυτό. Παραδείγματος χάριν, ο κανόνας παραγωγής:

b < a > c → aa

μετατρέπει το "a" σε "aa", αλλά μόνο αν το "a" εμφανίζεται μεταξύ ενός "b" και ενός "c" στη συμβολοσειρά εισόδου:

...bac...

Όπως συμβαίνει και με τις στοχαστικές παραγωγές, υπάρχουν πολλαπλές παραγωγές για το χειρισμό συμβόλων σε διαφορετικά περιβάλλοντα. Εάν δεν μπορεί να βρεθεί κανένας κανόνας παραγωγής για ένα δεδομένο πλαίσιο, θεωρείται η παραγωγή ταυτότητας και το σύμβολο δεν αλλάζει κατά τον μετασχηματισμό. Εάν υπάρχουν και οι δύο παραγωγές, η ευαίσθητη στο πλαίσιο και η χωρίς πλαίσιο, στην ίδια γραμματική, η ευαίσθητη στο πλαίσιο παραγωγή θεωρείται ότι υπερισχύει όταν είναι εφαρμόσιμη.

Παραμετρικές γραμματικές[Επεξεργασία | επεξεργασία κώδικα]

Σε μια παραμετρική γραμματική, κάθε σύμβολο στο αλφάβητο έχει μια λίστα παραμέτρων που συνδέεται με αυτό. Ένα σύμβολο σε συνδυασμό με τη λίστα παραμέτρων του ονομάζεται ενότητα, και μια συμβολοσειρά σε μια παραμετρική γραμματική είναι μια σειρά από ενότητες. Ένα παράδειγμα συμβολοσειράς μπορεί να είναι:

a(0,1)[b(0,0)]a(1,2)

Οι παράμετροι μπορούν να χρησιμοποιηθούν από τις λειτουργίες σχεδίασης, καθώς και από τους κανόνες παραγωγής. Οι κανόνες παραγωγής μπορούν να χρησιμοποιήσουν τις παραμέτρους χρησιμοποιώντας δύο τρόπους: πρώτον, σε μια δήλωση υπό όρους που καθορίζει αν θα εφαρμοστεί ο κανόνας και δεύτερον, ο κανόνας παραγωγής μπορεί να τροποποιήσει τις πραγματικές παραμέτρους. Παραδείγματος χάριν:

a(x,y) : x == 0 → a(1, y+1)b(2,3)

Η ενότητα a(x,y) υφίσταται μετασχηματισμό σύμφωνα με αυτόν τον κανόνα παραγωγής, εάν ικανοποιείται η συνθήκη x=0. Παραδείγματος χάριν, η a(0,2) θα υποστεί τροποποίηση, ενώ η a(1,2) όχι.

Στο τμήμα μετασχηματισμού του κανόνα παραγωγής, μπορούν να επηρεαστούν οι παράμετροι καθώς και ολόκληρες ενότητες. Στο παραπάνω παράδειγμα, η ενότητα b(x,y) προστίθεται στη συμβολοσειρά, με αρχικές παραμέτρους (2,3). Επίσης, οι παράμετροι της ήδη υπάρχουσας μονάδας μετασχηματίζονται. Σύμφωνα με τον παραπάνω κανόνα παραγωγής,

a(0,2)

Γίνεται

a(1,3)b(2,3)

καθώς η παράμετρος "x" της a(x,y) μετατρέπεται ρητά σε "1" και η παράμετρος "y" της a αυξάνεται κατά ένα.

Οι παραμετρικές γραμματικές επιτρέπουν τα μήκη γραμμών και οι γωνίες διακλάδωσης να καθορίζονται από τη γραμματική και όχι από τις μεθόδους ερμηνείας της χελώνας. Επίσης, αν η ηλικία δίνεται ως παράμετρος για μια ενότητα, οι κανόνες μπορούν να αλλάζουν ανάλογα με την ηλικία ενός τμήματος φυτού, επιτρέποντας τη δημιουργία κινούμενων εικόνων ολόκληρου του κύκλου ζωής του δέντρου.

Αμφίδρομες γραμματικές[Επεξεργασία | επεξεργασία κώδικα]

Το αμφίδρομο πρότυπο διαχωρίζει ρητά το συμβολικό σύστημα επαναγραφής από την ανάθεση σχήματος. Για παράδειγμα, η διαδικασία επαναγραφής συμβολοσειρών στο Παράδειγμα 2 (μορφοκλασματικό δέντρο) είναι ανεξάρτητη από τον τρόπο ανάθεσης γραφικών πράξεων στα σύμβολα. Με άλλα λόγια, ένας άπειρος αριθμός μεθόδων σχεδίασης είναι εφαρμόσιμος σε ένα δεδομένο σύστημα επαναγραφής.

Το αμφίδρομο πρότυπο αποτελείται από 1) μια προς τα εμπρός διαδικασία κατασκευάζει το δέντρο παραγώγισης με κανόνες παραγωγής και 2) μια προς τα πίσω διαδικασία υλοποιεί το δέντρο με σχήματα με βήμα προς βήμα (από τα φύλλα προς τη ρίζα). Κάθε βήμα αντίστροφης παραγώγισης περιλαμβάνει ουσιαστικό γεωμετρικο-τοπολογικό συλλογισμό. Με αυτό το αμφίδρομο πλαίσιο, οι περιορισμοί και οι στόχοι σχεδιασμού κωδικοποιούνται στη μετάφραση γραμματικής-σχήματος. Σε εφαρμογές αρχιτεκτονικού σχεδιασμού, η αμφίδρομη γραμματική διαθέτει συνεπή εσωτερική συνδεσιμότητα και πλούσια χωρική ιεραρχία^[7].

Αναπάντητα προβλήματα[Επεξεργασία | επεξεργασία κώδικα]

Υπάρχουν πολλά αναπάντητα προβλήματα που αφορούν μελέτες των συστημάτων-L. Παραδείγματος χάριν:

Καθορισμός όλων των προσδιοριστικών ελεύθερων πλαισιωμένων συστημάτων-L που είναι τοπικά κατειλημμένα (μια πλήρης λύση είναι γνωστή μόνο στην περίπτωση που υπάρχουν μόνο δύο μεταβλητές) ^[8].
Με δεδομένο μια δομή, να βρεθεί ένα σύστημα-L που μπορεί να παράγει αυτή τη δομή.

Βιβλιογραφία[Επεξεργασία | επεξεργασία κώδικα]

Przemysław Prusinkiewicz, Aristid Lindenmayer – The Algorithmic Beauty of Plants PDF version available here for free Αρχειοθετήθηκε 2021-04-10 στο Wayback Machine.
Grzegorz Rozenberg, Arto Salomaa – Lindenmayer Systems: Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology (ISBN 978-3-540-55320-5)
D.S. Ebert, F.K. Musgrave, et al. – Texturing and Modeling: A Procedural Approach, (ISBN 0-12-228730-4)
Burry, Jane, Burry Mark, (2010). The New Mathematics of Architecture, New York: Thames and Hudson.
Aristid Lindenmayer, "Mathematical models for cellular interaction in development Αρχειοθετήθηκε 2021-10-28 στο Wayback Machine.." J. Theoret. Biology, 18:280—315, 1968.

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

↑ «Lindenmayer-System». rue-a.github.io. Ανακτήθηκε στις 1 Νοεμβρίου 2023.
↑ Lindenmayer, Aristid (March 1968). «Mathematical models for cellular interactions in development II. Simple and branching filaments with two-sided inputs». Journal of Theoretical Biology 18 (3): 300–315. doi:10.1016/0022-5193(68)90080-5. ISSN 0022-5193. PMID 5659072. Bibcode: 1968JThBi..18..300L.
↑ Grzegorz Rozenberg and Arto Salomaa. The mathematical theory of L systems (Academic Press, New York, 1980). (ISBN 0-12-597140-0)
↑ «L-systems - Encyclopedia of Mathematics». encyclopediaofmath.org. Ανακτήθηκε στις 1 Νοεμβρίου 2023.
↑ Bachmair, Leo (30 Δεκεμβρίου 2006). Rewriting Techniques and Applications: 11th International Conference, RTA 2000, Norwich, UK, July 10-12, 2000 Proceedings. Springer. ISBN 978-3-540-44980-5.
↑ «L-systems». Encyclopedia of Mathematics. Springer. Ανακτήθηκε στις 26 Ιουλίου 2022.
↑ Hua, H., 2017, December. A Bi‐Directional Procedural Model for Architectural Design. In Computer Graphics Forum (Vol. 36, No. 8, pp. 219-231).
↑ Kari, Lila· Rozenberg, Grzegorz· Salomaa, Arto (1997). «L Systems». Handbook of Formal Languages. σελίδες 253–328. doi:10.1007/978-3-642-59136-5_5. ISBN 978-3-642-63863-3.

[1] «Lindenmayer-System». rue-a.github.io. Ανακτήθηκε στις 1 Νοεμβρίου 2023.

[2] Lindenmayer, Aristid (March 1968). «Mathematical models for cellular interactions in development II. Simple and branching filaments with two-sided inputs». Journal of Theoretical Biology 18 (3): 300–315. doi:10.1016/0022-5193(68)90080-5. ISSN 0022-5193. PMID 5659072. Bibcode: 1968JThBi..18..300L.

[3] Grzegorz Rozenberg and Arto Salomaa. The mathematical theory of L systems (Academic Press, New York, 1980). (ISBN 0-12-597140-0)

[4] «L-systems - Encyclopedia of Mathematics». encyclopediaofmath.org. Ανακτήθηκε στις 1 Νοεμβρίου 2023.

[5] Bachmair, Leo (30 Δεκεμβρίου 2006). Rewriting Techniques and Applications: 11th International Conference, RTA 2000, Norwich, UK, July 10-12, 2000 Proceedings. Springer. ISBN 978-3-540-44980-5.

[6] «L-systems». Encyclopedia of Mathematics. Springer. Ανακτήθηκε στις 26 Ιουλίου 2022.

[7] Hua, H., 2017, December. A Bi‐Directional Procedural Model for Architectural Design. In Computer Graphics Forum (Vol. 36, No. 8, pp. 219-231).

[8] Kari, Lila· Rozenberg, Grzegorz· Salomaa, Arto (1997). «L Systems». Handbook of Formal Languages. σελίδες 253–328. doi:10.1007/978-3-642-59136-5_5. ISBN 978-3-642-63863-3.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]