In der vorliegenden Arbeit wurde ein System in der Programmiersprache Python implementiert, das formale Sprachen durch Verwendung des Lernverfahrens Identification by Enumeration identifiziert. Dafür können der Anwendung positive und negative Beispielwörter in Form von Strings vorgelegt werden. Auf Basis der angebotenen Informationen erzeugt das Programm formale Grammatiken als Hypothesen. Abhängig von der Konfiguration können so rechtslineare Grammatiken oder Grammatiken in Chomsky-Normalform als Hypothesen entstehen. Das System ist so gestaltet, dass der Lernprozess an beliebig wählbaren Stellen unterbrochen und zu einem späteren Zeitpunkt verlustfrei fortgesetzt werden kann.

Um valide Hypothesen zu finden, verwendet das Programm Hypothesengeneratoren. Diese zählen Grammatiken auf und erzeugen so eine Hypothesenmenge, die linear nach einer konsistenten Hypothese durchsucht wird. Das Alphabet, auf dem die zu lernende Sprache aufgebaut ist, kann durch den Benutzer definiert werden. Die Aufzählung der Grammatiken ist durch die Nutzung mehrerer aufzählender Objekte implementiert. Diese sind ineinander verschachtelt, um Mengen von Produktionsregeln zu erzeugen, aus denen Grammatiken generiert werden. Jedes dieser Objekte zählt bestimmte Teilstücke der Produktionsregeln auf, die abschließend zu Mengen zusammengefasst werden. Insgesamt wurden Enumeratorenklassen für die folgenden sechs Aufzählungen implementiert: (1) Terminalsymbole, (2) Nichtterminalsymbole, (3) rechte Seiten von Produktionsregeln, (4) linke Seiten von Produktionsregeln, (5) Produktionsregeln und (6) Produktionsregelmengen. Da alle enumerierenden Objekte von einer Basisklasse erben, wurde eine Generik erreicht, die es erlaubt, Aufzählungen beliebig zu kombinieren und zu erweitern. Für die Überprüfung der Konsistenz der Hypothesen wurden zwei Verfahren realisiert. Dabei gilt es, das Wortproblem zu lösen. Werden rechtslineare Grammatiken gelernt, erfolgt das mit Hilfe von Akzeptoren. Dabei wird die Hypothese in einen DEA überführt und das Beispielwort in diesen eingegeben. Bei Grammatiken in CNF werden Methoden des Natural Language Tool Kits (NLTK) verwendet.

In den durchgeführten Tests war das System in der Lage, einfache a-b-Sprachen zu lernen. Für komplexere Sprachen und Sprachen mit größerem Alphabetumfang hat sich der implementierte Lernprozess allerdings als zu laufzeitintensiv herausgestellt. Als Hauptursachen dafür konnten die Erzeugung der Hypothesenmenge und deren Durchsuchung identifiziert werden. Die meisten der generierten Grammatiken enthielten Produktionsregeln, die aufgrund unterschiedlicher Nichtterminalsymbole auf ihren linken und rechten Seiten keine Wortableitungen bilden konnten. Dadurch erwies sich das lineare Durchsuchen des Hypothesenraumes als zu ineffizient. Im Ausblick der vorliegenden Arbeit werden Ideen skizziert, um die erkannten Probleme zu beheben. Im Fokus steht das Erzeugen von kanonischen Produktionsregelmengen. Zusätzlich soll das Durchsuchen einer einzigen großen Hypothesenmenge aufgeteilt werden. Hierbei entstehen mehrere Ad-hoc-Hypothesenräume, deren Ergebnisse vereinigt werden müssen.

In this thesis, a system was implemented in the Python programming language that identifies formal languages by using the identification by enumeration learning procedure. For this purpose, positive and negative examples of words can be presented to the application in the form of strings. Based on the information provided, the program generates formal grammars as hypotheses. Depending on the configurations of the system, right-linear grammars or grammars in Chomsky normal form can be created as hypotheses. The system is designed in such a way that the learning process can be interrupted at arbitrary points and continued at a later time without loss.

To find valid hypotheses, the program uses hypothesis generators. These enumerate grammars and thus generate a set of hypotheses that is searched linearly for a consistent hypothesis. The alphabet on which the language to be learned is built can be defined by the user. The enumeration of grammars is implemented by using multiple enumerating objects. These are arranged in a cascade to produce sets of production rules from which grammars are generated. Each of these objects enumerates specific components of the production rules which are finally combined into sets. In total, enumerator classes have been implemented for the following six components: (1) terminal symbols, (2) non-terminal symbols, (3) right-hand sides of production rules, (4) left-hand sides of production rules, (5) production rules and (6) production rule sets. Because all enumerating objects inherit from a base class, a genericity could be achieved which allows to combine and extend enumeration arbitrarily. To check the consistency of the hypotheses, two procedures were implemented. Therefore, the word problem has to be solved. If right-linear grammars are learned, the help of acceptors is required. For this purpose, the hypothesis is transferred into a DFA and the example word is entered into it. For grammars in CNF, methods of the Natural Language Tool Kit (NLTK) are used.

In the tests conducted, the system was able to learn simple a-b-languages. For more complex languages and languages with larger alphabets, however, the implemented learning process proved to be too runtime-intensive. As main reasons for this, the generation of the hypothesis set and its searching could be identified. Most of the generated grammars contained production rules that could not form word derivations due to different non-terminal symbols on their left-hand and right-hand sides. As a result, linear searching of the hypothesis set proved to be too inefficient. In the outlook of this thesis, ideas are outlined on how to solve the identified problems. The focus is on generating canonical production rule sets. Additionally, the search of a single large hypothesis set shall be split. In doing so, several smaller ad hoc hypothesis spaces are created whose results need to be unified.