Archiv des Autors: Kilian Evang

LaTeX, PSTricks, pdfTeX and Kile

5 Antworten

Many people writing scientific documents in TeX know the problem: on one hand, you want to use the more modern pdfTeX rather than LaTeX, for example because of the hyperref package or because you want to include pdf, png or jpg images. On the other hand, pdfTeX fails to produce figures that make use of PostScript, as is the case when using the very useful PSTricks. There are a number of possible ways around this problem. What is working well for me right now is a solution kindly provided by Wolfgang. Create PSTricks figures as separate documents using the following skeleton:

\documentclass{article}
\usepackage{pstricks}
\pagestyle{empty}
\begin{document}
% your graphics here
\end{document}

Then autocrop the document and save it as a PDF file using the following shell script:

#!/bin/sh

latex $1.tex
dvips $1.dvi
ps2eps -l --nohires -f $1.ps
ps2pdf -dEPSCrop -dAutoRotatePages=/None -dUseFlateCompression=true $1.eps

Then you can include the graphics (in PDF format) from your main document, which you build using pdfTeX.

Since I use Kile for writing in TeX, I replaced the shell script with a build tool which I called IlluTeX. It amounts to the following additions in ~/.kde/share/config/kilerc:

[Tool/IlluTeX/Default]
autoRun=no
checkForRoot=no
class=Sequence
close=no
jumpToFirstError=no
menu=Compile
sequence=LaTeX,DVItoPS,PStoEPS,PStoPDFEPSCrop,ViewPDF
state=Editor
to=pdf
type=Sequence

[Tool/PStoEPS/Default]
class=Convert
close=no
command=ps2eps
from=ps
menu=Compile
options=-l --nohires -f '%S.ps'
state=Editor
to=eps
type=Process

[Tool/PStoPDFEPSCrop/Default]
class=Convert
close=no
command=ps2pdf
from=eps
menu=Compile
options=-dEPSCrop -dAutoRotatePages=/None -dUseFlateCompression=true '%S.eps' '%S.pdf'
state=Editor
to=pdf
type=Process

Like/Gefällt mir/Мне нравится

7 Antworten

In a recent blog post, Geoffrey K. Pullum writes:

Twitter merely coined a verb meaning “send a message via Twitter”, but they didn’t specify what linguists call its subcategorization possibilities. They added the verb to the dictionary, but they didn’t specify its grammar. The verb tweet is gradually developing its own syntax according to what it means and what its users regard as its combinatory possibilities. That is a really interesting, though unintended, large-scale natural experiment in how syntactic change works. And it is running right now, every minute of every day.

If Facebook has, similarly to Twitter, coined a new verb, it’s probably like. Sure, that word existed before, but the way it’s employed on Facebook, it has developed an altogether new meaning. When you “Like” something on Facebook – i.e. you click the “Like” button – you thereby do not “like” it in the old sense – rather, you already liked it before and you now announce this to your friends. In the old sense of the verb, you are the experiencer of an affection. In the new sense, you are an agent, a deliberate performer of an action. The subject of the verb has a different thematic role in each case.

In the German translation of Facebook, the verb gefallen was chosen to translate like. This captures the old sense of like very well, much better than the perhaps more direct translation mögen. On the other hand, gefallen is having difficulties assuming the new sense, that of clicking a button to display one’s approval or enjoyment of something.

I think this is because gefallen assigns the experiencer role to its (dative) object rather than to its subject. For illustration, consider the English verb strike which does the same thing in sentences like “It strikes me that you are losing weight”: the verb is used to describe a situation where somebody experiences something, e.g. the striking perception that another person is losing weight, and the experiencer is described by the object of the sentence, e.g. me. Like is different; here, the experiencer is described by the subject of the sentence. Thus, when translating English like to German gefallen, the syntactic arguments need to be swapped: “I like this” becomes not “Ich gefalle das”, but “Das gefällt mir.”

Why does this prevent gefallen from assuming the new sense of its English counterpart like? Couldn’t “I recently liked that park on Facebook” analoguously translate to “Dieser Park hat mir neulich auf Facebook gefallen”? This sounds very weird to me, and I think the reason is a restriction on the mapping between thematic roles and syntactic arguments. Remember that the syntactic argument that was assigned the experiencer role in the old sense is assigned the agent role in the new sense. And to my knowledge, agent roles are only assigned to subjects in German (and also in English).1

If this were to change by gefallen acquiring a new sense where the dative object fills an agent role, this would pose many syntactic problems. How would you translate “Like this on Facebook!” or “I decided to like the park on Facebook” to German? Imperatives are always addressed to the (invisible) subject, and control always identifies the (invisible) subject of the embedded clause (“to like this park on Facebook”) with the subject or object of the embedding clause (“I decided”). One could construct “Der Park hat sich entschieden, mir auf Facebook zu gefallen”, but that would mean the park decided, not I.

So how do German speakers deal with the challenges posed by grammatically strenuous gefallen being the official translation of Facebook’s ubiquitous like?

First of all, as Facebook’s UI itself is concerned, “Like” and “Unlike” are translated quite freely with “Gefällt mir” (“I like”) and “Gefällt mir nicht mehr” (“I don’t like anymore”). This avoids using a new sense of the verb and rephrases things to use the old sense, by allowing the user to describe herself as an experiencer rather than explicitly offer her the possibility to become an agent. The description does not match reality perfectly, of course, for when I unlike something, that does not imply I don’t like it anymore, it just means I no longer want to commit to that on my Facebook profile.

In status updates about liking pages or links, the issue does not arise, as the English original itself talks about liking in the old sense, as an affectional state rather than an action. After all, it says “Peter Schwarz likes Conny Fuchs’s link”, not “Peter Schwarz liked Conny Fuchs’s link.” Interestingly, the relatively free word order of German makes it possible to keep the structure of such messages using gefällt, putting the dative object before the verb: “Peter Schwarz gefällt Conny Fuchs’ Link.”

Before the verb is even the preferred position for the experiencer in most contexts. Nevertheless, the prototypical main clause word order in German still starts with the subject. And person names are not marked for dative case.2 So the above could also be read with Peter Schwarz as the subject and Conny Fuchs’s link as the object. When Facebook’s “Gefällt mir” button started becoming ubiquitous on the German-speaking Internet, I actually expected people to start using gefallen exactly like like in the new sense, with an agent subject and a theme accusative object. It is not unusual for German verbs to assume semantic and syntactic argument structures from English counterparts, which is then bemoaned as an Anglicism once it has irreversibly settled in. An example is the verb erinnern (remember). The standard way to say “I remember this” in German is “Ich erinnere mich daran”, with an accusative reflexive pronoun and a prepositional object. However, recently “Ich erinnere das”, with the same structure as in English, is also frequently heard. Or maybe this non-standard usage has been around forever and I’m just interpreting it as a new Anglicism. (See johannes’s comment below.) To come back to my point, no, I haven’t seen or heard gefallen used with the argument structure of like yet. The new sense of like doesn’t seem to have a lexical counterpart in German yet.

Instead, gefallen is used with a slightly different sense in the context of Facebook – “Mir gefällt das” not meaning that I like it but that I made liking it part of my Facebook profile – but with the same argument structure (experiencer subject, theme dative object, no agent), still describing a state, not an action. As long as the context does not absolutely require an agent, gefallen in this sense is used rather consistently, as some of tonight’s first Google hits for „auf facebook gefallen“ show:

  • Wenn dir beispielsweise etwas wie ein Buch, ein Film oder jemand wie ein Sportler gefällt, wird diese Verbindung genauso Teil deines Profils wie dies der Fall ist, wenn dir Seiten auf Facebook gefallen. (Facebook Help Center)
  • High Live  würde sich freuen, wenn noch mehr Leuten „High Live“ auf Facebook „gefallen“ würde… (High Live’s page)
  • Die Seiten oder Produkte, die Mitgliedern auf Facebook gefallen, generieren automatisch entsprechende Vorschläge auf Amazon. (Social Media Pro)
  • Wir haben für euch auf Facebook eine einige Seiten erstellt, die für Spieler gedacht sind, denen unsere Seiten zu Blizzard, Diablo, StarCraft und Warcraft auf Facebook gefallen. (BlizzCon 2010)

There are some bewitchingly creative variations:

  • Gaggle ist auf diversen Plattformen präsent, über YouTube gibt es Gaggle-Videos, über Facebook werden neueste Nachrichten aus dem Gaggle-Kosmos ausgetauscht, 1253 Personen gefällt das. (Die Zeit)
  • 313’000 Personen finden auf Facebook gefallen an Swarovski. (fuellhaas.com)

And the ultimate solution to the problem that the one who clicks “Like” is not a subject in such constructions has been found by YouTube user Clixoom. He uses a “causative” construction with lassen, enabling him to use gefallen in an imperative statement:

  • lasst euch Clixoom auf FACEBOOK „gefallen“

This is also a creative new use of the phrase “sich etwas gefallen lassen”. The above invitation to like Clixoom on Facebook can also be read as a self-mocking invitation to put up with Clixoom on Facebook.

1 If you don’t count “logical subject” phrases in passive as objects of the verb, which you shouldn’t.

2 In Russian they are, and Facebook doesn’t seem to know how to do that yet even for Russian names written in Cyrillic, which is kind of lame and leads to lots of grammatically incorrect status updates, since the Russian like, нравиться, works pretty much exactly like gefallen.

Wort des Tages: Zwei-Komponenten-Tauschratte

Schreibe eine Antwort

Eine Tauschratte ist ein Nagetier, das Gegenstände mitnimmt und dafür manchmal andere hinterlässt.

Im übertragenen Sinne ist eine Tauschratte auch irgendjemand oder irgendetwas, der/die/das etwas wegnimmt und etwas anderes an dessen Stelle setzt.

Dieser Begriff ist z.B. auch dann anwendbar, wenn eine Person etwas wegnimmt und eine andere Person zeitnah etwas anderes an dieselbe Stelle setzt. Diese beiden Personen bilden dann eine Zwei-Komponenten-Tauschratte.

Zwischen Kontextfreiheit und Kontextsensitivität, Teil 3: Nicht kontextfreie Grammatiken für Fragmente natürlicher Sprachen

3 Antworten

Kontextfreie Grammatiken sind sehr beliebt für die Beschreibung natürlicher Sprachen. Zumindest in der Theorie und solange es nicht zu kompliziert wird, eignen sie sich gut dafür, Syntax in den Griff zu kriegen. Warum interessieren sich manche Computerlinguistien dann so für nicht kontextfreie Grammatikformalismen wie SRCG, das ich in Teil 1 vorgestellt und in Teil 2 in die Chomsky-Hierarchie eingeordnet habe?

Schauen wir uns ein Fragment der deutschen Sprache an, das aus Nebensätzen wie diesen besteht:

(1.1) dass wir das Haus anstreichen
(1.2) dass wir dem Hans das Haus anstreichen helfen
(1.3) dass wir die Kinder dem Hans das Haus anstreichen helfen lassen

Es wird z.B. durch die folgende kleine kontextfreie Grammatik mit Startsymbol S‘ beschrieben. Von Finitheit, Numerus und Genus sehen wir mal großzügig ab und beachten nur Kasus (n für Nominativ, d für Dativ, a für Akkusativ):

(2.1) S‘ → C S
(2.2) S → NPn VP
(2.3) VP → NPa Va
(2.4) VP → NPd VP Vdv
(2.5) VP → NPa VP Vav
(2.6) NPn → PRPn
(2.7) NPa → Da N
(2.8) NPd → Dd N
(2.9) C → dass
(2.10) PRPn → wir
(2.11) Da → das
(2.12) Dd → dem
(2.13) N → Haus
(2.14) N → Hans
(2.15) N → Kinder
(2.16) Va → anstreichen
(2.17) Vdv → helfen
(2.18) Vav → lassen

Die Grammatik beschreibt Sätze wie in (1.1-3) nicht nur, sie liefert auch linguistisch plausible Strukturen dafür. Erstens trägt sie der Beobachtung Rechnung, dass Sprache wie Lego ist: Sätze sind aus Teilen (Phrasen oder Konstituenten) zusammengesetzt, die ihrerseits wiederum aus Phrasen bestehen, bis man bei den kleinsten Bausteinen anlangt, den Wörtern. Phrasen gleicher Kategorie sind untereinander austauschbar. Z.B. sind sowohl das Haus anstreichen als auch dem Hans das Haus anstreichen helfen Verbalphrasen (VP) und können daher beide auf dass wir folgen und einen Satz bilden (1.1, 1.2), auch wenn sie in sich unterschiedlich aufgebaut sind, einmal nach Regel (2.3) und einmal nach Regel (2.4). Umgekehrt kann dieselbe Konstituente, z.B. das Haus anstreichen in verschiedenartigen Kontexten auftauchen (1.1, 1.2., 1.3), weil sowohl (2.2) als auch (2.4) als auch (2.5) das VP-Symbol auf der rechten Seite haben.

Zweitens modellieren die Regeln die lokalen Abhängigkeiten zwischen Verben und ihren Argumenten: helfen ist zum Beispiel ein Verb, das eine Nominalphrase im Dativ als Argument nehmen kann (wem man hilft) sowie eine Verbalphrase (wobei man hilft). Ich habe das in der Grammatik mal so kodiert, dass helfen die Kategorie Vdv hat (Verb mit Dativ-Nominalphrase und Verbalphrase). Analog ist lassen Vav (Akkusativ-Nominalphrase, wen oder was man lässt; Verbalphrase, was man ihn, sie oder es tun lässt) und streichen nur Va (Akkusativ-Nominalphrase, was man streicht). Regeln 2.3-5 sorgen dafür, dass jede Verbalphrase mit einem Verb (dem Kopf der Phrase) und dazu passenden Argumenten aufgebaut wird.

Ein Ableitungsbaum veranschaulicht die syntaktische Struktur eines Satzes, hier die von (1.3):

Kontextfreier Ableitungsbaum für den Satz „dass wir die Kinder dem Hans das Haus anstreichen helfen lassen“

Übersetzen wir nun unsere drei Beispielsätze ins Zürichdeutsche nach Shieber (1985):

(3.1) das mer es huus aastriche
(3.3) das mer em Hans es huus hälfe aastriche
(3.3) das mer d’chind em Hans es huus lönd hälfe aastriche

Es fällt auf, dass die Verben am Ende in der umgekehrten Reihenfolge stehen. Wenn wir weiterhin davon ausgehen, dass z.B. in (3.3) d’chind direkt mit lönd zusammenhängt, em Hans direkt mit hälfe und es huus direkt mit aastriche, was zweifellos sinnvoll ist, dann stellen wir fest, dass unsere Verbalphrasen nicht mehr verschachtelt sind wie im Hochdeutschen, sondern sich „überkreuzen“. Ein Baumdiagramm zu (3.3) sieht dann so aus:

Ableitungsbaum mit kreuzenden Kanten zu dem Satz „das mer d’chind em Hans es huus lönd hälfe aastriche“

Man spricht auch von unterbrochenen Konstituenten, weil zwischen den Wörtern, die zu den niedrigeren beiden VPs gehören, Wörter auftauchen, die nicht dazu gehören.

Es ist einigermaßen offensichtlich, dass das keine kontextfreie Ableitung mehr ist. Eine 2-SRCG dazu indes gibt es:

(4.1) S’(XY) → C(X) S(Y)
(4.2) S(XYZ) → NPn(X) VP(Y,Z)
(4.3) VP(XY,ZU) → NPa(X) VP(Y,U) Vav(Z)
(4.4) VP(XY,ZU) → NPd(X) VP(Y,U) Vdv(Z)
(4.5) VP(X,Y) → NPa(X) Va(Y)
(4.6) NPn(X) → PRPn(X)
(4.7) NPd(XY) → Dd(X) N(Y)
(4.8) NPa(XY) → Da(X) N(Y)
(4.9) C(das) → ε
(4.11) PRPn(mer) → ε
(4.12) Dn(d’) → ε
(4.13) Dd(em) → ε
(4.13) N(huus) → ε
(4.14) N(Hans) → ε
(4.15) N(chind) → ε
(4.16) Va(aastriche) → ε
(4.17) Vdv(hälfe) → ε
(4.18) Vav(lönd) → ε

Die Idee ist, VPs zwei Argumente zu geben, das erste für die Argumente der Verben, das zweite für die Verben selbst. Hängt von einer Verbalphrase VP1 eine zweite Verbalphrase VP2 ab, bilden die Argumente von VP2 die Basis, VP1 hängt ihr NP-Argument und ihr Verb jeweils vorne an, wie in Regeln (4.3-4) zu sehen.

Eine VP in dieser Grammatik ist auch nicht nur einfach eine Aneinanderreihung von Nominalphrasen, gefolgt von einer gleich langen Aneinanderreihung von Verben – das würde man zur Not auch noch mit einer kontextfreien Grammatik hinkriegen, wenn auch mit einer anderen Struktur (vgl. die erste Beispielgrammatik in Teil 1). Nein, die Regeln „checken“ ja, ob eine Nominalphrase zum Verb passt (z.B. Dativ für helfen, aber Akkusativ für lassen). Falsche Sätze wie dieser sind nicht ableitbar (lönd verlangt Akkusativ, nicht Dativ):

(5.1) *das mer em chind em Hans es huus lönd hälfe aastriche

Das ist der Kern des Arguments von Shieber (1985) dafür, dass natürliche Sprachen im Allgemeinen nicht kontextfrei sind.

In Teil 4: Was man dagegen einwenden kann und warum es so oder so nützlich sein kann, unterbrochene Konstituenten (also ein wenig Kontextfreiheit) bei der Analyse natürlicher Sprachen zuzulassen.

Sehr konkrete Pläne habe ich für Teil 4 noch nicht. Erst mal bin ich gespannt, ob meine werten Leser Fragen und Kommentare hierzu haben und wenn ja, welche. Daraus ergibt sich dann vielleicht eine klarere Vision für Teil 4.

Literatur

Marcus Kracht: The Mathematics of Language. Gruyter, 2003.

Stuart M. Shieber: Evidence against the Context-freeness of Natural Language. In: Linguistics and Philosophy 8, 1985.

s.a. Literatur zu Teil 1 und Teil 2.

Krasse Aufzüge (2)

2 Antworten

Haußerstraße, Tübingen: Ein steiler grüner Garten mit einem schmucken gelben Gartenhäuschen vor einem schmucken gelben Haupthaus, dazu eine… Gartenachterbahn? Man wähnt sich in einem Vergnügungspark…

…bis man die Anlage eines Tages in Betrieb sieht. Es handelt sich um einen gigantischen Treppenlift.

Zwischen Kontextfreiheit und Kontextsensitivität, Teil 2: Eine erweiterte Chomsky-Hierarchie

6 Antworten

Ausgelöst durch Prüfungsvorbereitung und Schreiben an der Masterarbeit habe ich mich in letzter Zeit viel mit Typen formaler Grammatiken beschäftigt, die alle kontextfreien Sprachen beschreiben können und darüber hinaus einige, aber nicht alle kontextsensitiven Sprachen. Einen solchen Grammatikformalismus, nämlich Simple Range Concatenation Grammars (SRCG), habe ich in Teil 1 dieser Serie vorgestellt. In Teil 3 werde ich Anwendungen auf natürliche Sprache skizzieren.

Heute ist Teil 2 dran und damit die Vogelperspektive: Wo stehen wir auf der Chomsky-Hierarchie der formalen Sprachen? Ich kopiere dazu einfach Herrn Raus Übersicht über die Chomksy-Hierarchie, füge aber zwei weitere Stufen, also zwei weitere Klassen von Sprachen ein.

  • Chomsky 0: Alle Sprachen, die sich überhaupt durch eine Grammatik beschreiben lassen.
  • Chomsky 1: Eine Teilmenge davon, nämlich die Sprachen, die sich durch eine kontextsensitive Grammatik beschreiben lassen.
  • PTIME aka P: Die Sprachen, bei denen das Wortproblem in Polynomialzeit entscheidbar ist. Range Concatenation Grammars (RCG) können genau diese Sprachen beschreiben. PTIME ist eine Teilmenge von Chomsky 0; ist es auch eine Teilmenge von Chomsky 1? Ich weiß es nicht, vielleicht weiß es auch niemand, aus dieser Übersicht geht es jedenfalls nicht hervor. Für Aufklärung bin ich dankbar.
  • Eine Teilmenge sowohl von Chomksy 1 als auch von PTIME sind die Sprachen, die sich durch Simple Range Concatenation Grammars (SRCG) beschreiben lassen. So weit ich weiß, hat diese Klasse von Sprachen keinen einschlägigen Namen. SRCG ist eine eingeschränkte Variante von RCG, aber immer noch deutlich mächtiger als kontextfreie Grammatiken (CFG). Es gehört zu den so genannten „schwach kontextsensitiven“ (mildly context-sensitive) Grammatikformalismen, die vor allem im Zusammenhang mit natürlicher Sprache interessant sind – wo kontextfreie Grammatiken für eine adäquate Beschreibung nicht mehr ausreichen, man aber wegen Effizienz und Theoriedesign auch nicht zu weit darüber hinausgehen will. Dieselbe Klasse von Sprachen lässt sich durch die mit SRCG auch sonst so gut wie identischen Formalismen Linear Context-free Rewriting Systems (LCFRS) und Multiple Context-free Grammars (MCFG) beschreiben.
  • Chomsky 2: Eine Teilmenge davon, nämlich die Sprachen, die sich durch eine kontextfreie Grammatik beschreiben lassen.
  • Chomsky 3: Eine Teilmenge davon, nämlich die Sprachen, die sich durch eine reguläre Grammatik beschreiben lassen.

Die originale vierstufige Chomksy-Hierarchie bietet ein schönes Zwiebelschalenmodell, bei dem jede Sprachenmenge die nächste strikt einschließt:

A graphical representation of the sets of languages included in the Chomsky hierarchy.Diese Schönheit habe ich durch mein Unwissen, ob PTIME eine Teilmenge von Chomsky 1 ist, zerstört. Bedenkt man aber, dass Chomsky 1, also die Klasse der kontextsensitiven Sprachen, meines Wissens weder theoretisch noch praktisch besonders interessante Eigenschaften hat, kann man sie rausschmeißen und aus der obigen Auflistung durchaus wieder eine schöne Zwiebel basteln:

A graphical representation of five sets of languages: recursively enumerable, PTIME, SRCG, context-free and regularDoch Vorsicht: In einem Vortrag habe ich einmal ein entsprechendes Diagramm für die verschiedenen schwach kontextsensitiven Grammatikformalismen gesehen, die es heute so gibt. Es sah ungefähr so aus:

Einander wirr überschneidende Ellipsen

In Teil 3: Warum man arguably schwach kontextsensitive Grammatikformalismen braucht, um natürliche Sprache zu beschreiben.

Nachbemerkung 1: mildly context-sensitive klingt schwammig, ist aber relativ präzise definiert. Der Begriff bezieht sich im Gegensatz z.B. zu context-sensitive und context-free nicht auf Sprachen, sondern auf Mengen von Sprachen. Eine Menge von Sprachen ist schwach kontextsensitiv genau dann, wenn sie einerseits alle kontextfreien Sprachen enthält und überdies kreuzende Abhängigkeiten beschreiben kann (siehe dazu Teil 3), andererseits aber nur Sprachen enthält, die in polynomieller Zeit parsbar sind (also eine Teilmenge von PTIME ist) und überdies konstantes Wachstum aufweisen. Für Details siehe Joshi (1985) oder Kallmeyer (2010). Trotz dieser präzisen Definition gibt es noch keinen Grammatikformalismus, von dem man wüsste, dass er die größtmögliche schwach kontextsensitive Menge von Sprachen beschreibt. Obwohl SRCG nach heutigem Kenntnisstand der mächtigste schwach kontextsensitive Formalismus ist, kann es also gut sein, dass es eine schwach kontextsensitive Menge von Sprachen gibt, die Sprachen enthält, die SRCG nicht beschreiben kann.

Nachbemerkung 2: Joshi (1985) hat mildly context-sensitive als terminus technicus eingeführt und, so bilde ich mir ein, extra nicht weakly genommen, weil dieses Wort im Zusammenhang mit formalen Grammatiken schon eine ganz andere Bedeutung hat, nämlich bei schwacher Äquivalenz. Deswegen finde ich die deutsche Übersetzung schwach kontextsensitiv etwas unglücklich. Hätte man nicht gelinde kontextsensitiv nehmen können?

Nachbemerkung 3: Wo wir schon bei Terminologiekritik sind. Das Begriffspaar kontextfrei und kontextsensitiv hat mich schon immer geärgert. Das klingt so komplementär. Tatsächlich ist aber jede kontextfreie Sprache auch eine kontextsensitive Sprache, siehe Zwiebel. Diese begriffliche Verwirrung ist ein Grund mehr, sich mit der Klasse der kontextsensitiven Sprachen überhaupt nicht mehr zu beschäftigen. *g*

Literatur

Aravind K. Joshi: Tree adjoining grammars: How much context-sensitivity is required to provide reasonable structural descriptions? In: D. Dowty, L. Karttunen und A. Zwicky (Hrsg.), Natural Language Parsing, Cambridge University Press, 1985.

s.a. Literatur zu Teil 1

Zwischen Kontextfreiheit und Kontextsensitivität, Teil 1: Crashkurs Simple Range Concatenation Grammars (SRCG)

4 Antworten

In Herrn Raus Blog gibt es eine schöne mehrteilige Einführung in formale Sprachen, formale Grammatiken und die Chomksy-Hierarchie. Unter anderem werden dort reguläre Grammatiken, kontextfreie Grammatiken und kontextsensitive Grammatiken vorgestellt. Ich will heute einen weniger bekannten Grammatikformalismus vorstellen: Simple Range Concatenation Grammars (SRCG) (zu deutsch etwa: einfache Intervallverkettungsgrammatiken).

SRCGs können alle kontextfreien Sprachen beschreiben und darüber hinaus einige, aber nicht alle kontextsensitiven Sprachen. Genaueres dazu sage ich in Teil 2 dieser Serie, bevor ich in Teil 3 andeute, wozu das speziell bei natürlichen Sprachen (also so etwas wie Englisch, Deutsch, Niederländisch oder Zürichdeutsch) und damit für die Computerlinguistik von Nutzen sein kann.

Fangen wir mit einer guten alten kontextfreien Grammatik an. Hier sind die Regeln einer kontextfreien Grammatik, die die Sprache {anbn|n≥0} erzeugt, also die Sprache, die aus den Wörtern ε (das leere Wort), ab, aabb, aaabbb usw. besteht.

(1.1) S → aSb
(1.2) S → ε

Wenn wir diese Grammatik als SRCG schreiben, sehen die Regeln so aus:

(2.1) S(aXb) → S(X)
(2.2) S(ε) → ε

Vergleichen wir Regeln (1.1) und (2.1): Beide Regeln besagen, dass man aus dem Symbol S alle Wörter ableiten kann, die mit a losgehen, in der Mitte aus etwas bestehen, das man wiederum aus S ableiten kann, und mit b enden. Die Beschreibung „dessen, was man ableiten kann“, steht bei SRCG nicht auf der rechten Seite des Pfeils, sondern in Klammern neben dem Symbol der linken Seite. Es wird die Variable X verwendet, die auf der rechten Seite in dem Ausdruck S(X) wieder auftaucht: Der sagt, dass X etwas sein muss, das man aus S ableiten kann.

Regel (2.2) besagt wie Regel (1.2), dass man aus S den leeren String ableiten kann, und zwar bedingungslos – es tauchen keine weiteren Symbole auf, deswegen ist auch die rechte Seite leer (geschrieben wie der leere String als ε).

Eine andere SRCG für dieselbe Sprache wäre die hier:

(3.1) S(XY) → A(X, Y)
(3.2) A(aX, bY) → A(X, Y)
(3.3) A(ε, ε) → ε

Hier taucht ein neues Nichtterminal auf, A. Was hinter A in Klammern steht, besteht aus zwei Teilen, man sagt: A ist zweistellig oder: A hat zwei Argumente. Eins für den a-Teil der Wörter und eins für den b-Teil.

Damit sind wir beim wesentlichen Unterschied zwischen SRCG und CFG: In CFGs kann man aus einem Nichtterminal einen Teilstring des Wortes ableiten, in SRCGs auch mehrere Teilstrings, technisch ausgedrückt: Tupel von Teilstrings.

Die Grammatik im Beispiel funktioniert so: Regel (3.3) sagt, dass aus A das Tupel ⟨ε, ε⟩ ableitbar ist, also zweimal der leere String. Regel (3.2) sagt: Wenn aus A das Tupel ⟨X, Y⟩ ableitbar ist (rechte Seite), dann ist aus A auch das Tupel ⟨aX, bY⟩ ableitbar (linke Seite). Generativ, prozedural und salopp ausgedrückt klatscht diese Regel vorne an das erste Argument von A ein a und an das zweite ein b. Diesen Prozess kann man beliebig oft wiederholen, bis man so viele a’s und b’s hat, wie man will – aber immer für beide Argumente gleichzeitig, sodass die Anzahl der a’s und b’s gleich bleibt. Schließlich kommt Regel (3.1) zum Zuge, die die beiden Argumente von A in das einzige Argument von S konkateniert (verkettet).

Man kann diesen Prozess auch in der umgekehrten Reihenfolge schreiben, als Ableitung. Eine Ableitung beginnt mit dem Startsymbol und dem Wort, das man ableiten will, und gelangt über die Anwendung von Regeln zu ε. Hier eine beispielhafte Ableitung für das Wort aabb:

S(aabb)  ⇒(3.1) A(aa, bb)  ⇒(3.2) A(a, b)  ⇒(3.2) A(ε, ε)  ⇒(3.3) ε

Weil jede Ableitung mit genau einem String beginnt (eben dem Wort, das man ableiten will), muss das Startsymbol immer einstellig sein. Die Stelligkeit ist für jedes Nichtterminal festgelegt, d.h. innerhalb einer Grammatik kann A z.B. nicht einmal mit zwei und einmal mit drei Argumenten auftauchen.

Während sich bei jeder Anwendung einer CFG-Regel an einer Stelle im abzuleitenden Wort etwas ändert – ein Nichtterminal wird durch etwas ersetzt – kann sich bei der Anwendung einer SRCG-Regel an mehreren Stellen etwas ändern. So ändert sich bei jeder Anwendung unserer Regel (3.2) sowohl vorne etwas (ein a wird hinzugefügt) als auch in der Mitte (ein b wird hinzugefügt). Leicht lässt sich das auf drei Stellen ausdehnen, sodass die Grammatik die Sprache {anbncn|n≥1} beschreibt, für die es schon keine CFG mehr gibt. Man gibt A einfach ein drittes Argument:

(4.1) S(XYZ) → A(X, Y, Z)
(4.2) A(aX, bY, cZ) → A(X, Y, Z)
(4.3) A(ε, ε, ε) → ε

Das ist jetzt eine so genannte 3-SRCG, d.h. eine SRCG, wo die Nichtterminale maximal 3 Argumente haben. Die Zeitkomplexität des Wortproblems (algorithmisch zu bestimmen, ob ein gegebenes Wort zu der von der Grammatik erzeugten Sprache gehört) nimmt für k-SRCGs mit steigendem k exponenziell zu (übrigens auch mit der maximalen Länge der rechten Regelseite, die bisher in allen Beispielen 0 oder 1 war). CFGs entsprechen 1-SRCGs, wie ganz oben illustriert, wo wir eine CFG direkt in eine 1-SRCG übersetzt haben.

Für die Form der Regeln einer SRCG gibt es zwei wichtige Einschränkungen: Auf der rechten Seite muss jedes Argument nicht mehr und nicht weniger als eine Variable enthalten (während auf der linken Seite Folgen von Terminalen, Variablen oder auch ganz leere Argumente erlaubt sind). Außerdem muss jede Variable, die in einer Regel vorkommt, auf der linken und auf der rechten Seite der Regel je genau einmal vorkommen. Ohne diese Einschränkungen hätte man die noch einmal deutlich mächtigeren und komplexeren Range Concatenation Grammars (RCG) (Boullier 1998).

In Teil 2 schauen wir uns etwas genauer an, welche Klassen von Sprachen SRCG und RCG beschreiben und wo man diese auf der Chomksy-Hierarchie einordnen kann.

Nachbemerkung 1: Aus pädagogischen Gründen habe ich immer „Regel“ und „Nichtterminal“ geschrieben, im RCG-Jargon sagt man eigentlich „Klausel“ und „Prädikat“ dazu. Wer schon einmal in Prolog programmiert hat, bei der klingt jetzt vielleicht ein Glöcklein. Ja, eine (S)RCG lässt sich mit trivialen Änderungen in der Syntax als Logikprogramm lesen. Leider ist das dann noch lange kein praxistauglicher Parser, wie ja auch Prologs im Kern kontextfreie Definite Clause Grammars (DCG) gewissen Beschränkungen unterworfen sind. Parsing-Algorithmen für RCG, SRCG und weitere Formalismen gibt’s in Kallmeyer (2010).

Nachbemerkung 2: Das war jetzt gewissermaßen auch eine Einführung in Linear Context-free Rewriting Systems (LCFRS) (Vijay-Shanker et al. 1987, Weir 1988) und Multiple Context-free Grammars (MCFG) (Seki et al. 1991). Diese beiden Grammatiktypen beschreiben dieselbe Klasse von Sprachen wie SRCG und unterscheiden sich auch sonst nur minimal davon.

Literatur

Pierre Boullier: A Generalization of Mildly Context-Sensitive Formalisms. In: Proceedings of the Fourth International Workshop on Tree-Adjoining Grammars and Related Formalisms (TAG+4), University of Pennsylvania, 1998.

Laura Kallmeyer: Parsing beyond Context-Free Grammars. Springer, 2010.

Hiroyuki Seki, Ryuichi Nakanishi, Yuichi Kaji, Sachiko Ando und Tadao Kasami: On Multiple Context-Free Grammars. In: Theoretical Computer Science 88(2), 1991.

K. Vijay-Shanker, David J. Weir und Aravind K. Joshi: Characterizing Structural Descriptions Produced by Various Grammar Formalisms. In: Proceedings of ACL, Stanford, 1987.

David J. Weir: Characterizing Mildly Context-Sensitive Grammar Formalisms. Dissertation, University of Pennsylvania, 1988.

Leistungsträger und Leistungsverweigerer

Eine Antwort

Zwei Schlagwörter und meine zwei Cent

Du bist also klug, fleißig und hast dein Leben im Griff. Deine Fähigkeiten, flexibel zu sein, die richtigen Ideen zu haben und bei der Sache zu bleiben bescheren dir wirtschaftlichen Erfolg. Du magst es, für dich selbst verantwortlich zu sein. Bevormundung ist dir ein Gräuel. Ich sympathisiere!

Was die Gesellschaft betrifft, so hältst du dich für einen ihrer Leistungsträger. Die günstigen Bedingungen, die sie deinem Aufstieg geboten hat, hast du natürlich gern angenommen. Andere an den Früchten deiner Arbeit teilhaben zu lassen, siehst du aber nicht ein. Wer deine Fähigkeiten und deinen Erfolg nicht hat, hat deiner Meinung nach die Pflicht zu verelenden, damit sich deine Leistung „wieder lohnt“. Du erhebst deine Fähigkeit zur Selbstverantwortlichkeit zur Ideologie, verdrängend, dass auch du einmal nicht mehr können könntest. Steuern und Abgaben würdest du daher am liebsten ganz abschaffen. Tatsächlich bist du also ein Leistungsverweigerer.

My Favorite Language Resources on the Web

2 Antworten
  • LEO is the online dictionary for native speakers of German. It has English, French, Mandarin Chinese, Italian, Spanish and Russian. I use it for the first three. LEO is very basic, it just gives you a list of all translations for a word or phrase with no ranking and very little information about usage and context. But the lists are often quite complete, it’s fast and there is also a message board that sometimes has useful additional translations and usage information. Here, as with everything on the Internet, using one’s brain while looking things up is important (as opposed to trusting the next best piece of information blindly).
  • Recently, I have frequently found English words on dict.cc which were missing from LEO.
  • The English Wiktionary has vast amounts of information on Chinese characters and their usage in Mandarin Chinese.
  • A third source for Chinese is Arch Chinese, which I use mainly for stroke orders, and sometimes for decomposition into radicals. The latter is done great here in principle, but alas, it’s quite incomplete.
  • Linguee is a new and hot thing with clever use of language technology. You can search English/German parallel corpora and see how others have solved the problem of translating XYZ. Now also available for English/Spanish, English/French and English/Portuguese.
  • If you already have an idea of how to put something and want to check it against text written by others,  or when you just want to get an idea of how a word is used, Google is a classic of course. With some (especially rare) words, the 1,000,000,000 dictionary sites out there tend to get in the way though and clutter up the first few results pages – when what you want is precisely not a dictionary, but unedited real-life usage. For that purpose, I have defined the Serchilo command “Google as a concordancer”, which filters out all dictionary sites I have discovered so far. Even if you are not yet using Serchilo as your default “search engine” (which you should), you can use the command by typing serchilo.net/cong yourword in your browser’s address bar.
  • As a grammar geek, I love the Logos Universal Conjugator, a vast archive of verb inflection tables in many languages. I mainly use it for French and Latin, when I need a more outlandish form of an irregular verb (or of a regular verb, for that matter) that I never bothered to remember thoroughly.

Dear readers, what are your favorite online tools for mastering foreign tongues?

Krasse Aufzüge (1)

8 Antworten

Da geht man in Bilbao (Spanien) nichts ahnend einen Weg am Hang entlang. Plötzlich taucht links eine Brücke auf, knickt ein paarmal ab und verschwindet im Gebüsch. Neugierig folgt man ihr und findet einen Aufzug, der kaminartig aus einem Haus herausragt. Damit kann man für ein paar Cent in die Altstadt fahren.