Skip to main content
11 votes
Accepted

Why isn’t it obvious that the grammars of natural languages cannot be context-free?

Imagine a very simple CFG that only handles nouns and verbs. S → N V N → dogs | cats | Alice | Bob V → walk | play | eat Right now this can't handle agreement. But it can with a small change: S → ...
Draconis's user avatar
  • 66.8k
4 votes
Accepted

What language does S -> A generates?

To answer this, follow the definitions. From Wikipedia (see further references there): The language of a grammar is the set of sentences it builds. A sentence is a sentential form that contains no ...
Keelan's user avatar
  • 4,223
4 votes

Why isn’t it obvious that the grammars of natural languages cannot be context-free?

Nothing in mathematics is ever obvious until after it is proven. 1.1 This is one reason English not being a CFG is not "obvious". A right-linear grammar can generate English, because a ...
user6726's user avatar
  • 83.1k
3 votes

Natural languages, programming languages, and information theory

As I interpret your question, you propose an alternative theory of syntax to CFG for linguistics. It's a thought, but do you have any evidence? I didn't see any. Don't you think you should have ...
Greg Lee's user avatar
  • 12.5k
2 votes

Is English modeled as a deterministic CFL or a CFL?

No natural language is deterministic. What book mentions LR parsers for English? There might be some “controlled languages” based on English that are deterministic, but a broad-coverage parser is ...
Atamiri's user avatar
  • 2,590
1 vote

Natural languages, programming languages, and information theory

The situation with natural languages is more convoluted because the analysis of sentences crucially depends on background knowledge, which makes use of metaphors, metonymy etc. widespread. Consider ...
Atamiri's user avatar
  • 2,590
1 vote

Natural languages, programming languages, and information theory

If you are thinking of formal language theory to compare programming languages and human languages, make sure you compare apples to apples. Don't mix up what a program can compute with what grammar ...
Mitch's user avatar
  • 4,465

Only top scored, non community-wiki answers of a minimum length are eligible