Questions tagged [context-free-grammars]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
5 votes
2 answers
2k views

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

I've read that a context-free grammar is one in which every production rule is written in the way V -> a, where V is a non-terminal symbol and a is a chain of non-terminal and terminal symbols. In ...
Qwertuy's user avatar
  • 703
2 votes
0 answers
32 views

Freely available Penn-Treebank-like Rewriting Rules corpus?

Hey I'm currently working on my thesis in computer science. For one of my experiments I need a large context-free grammar (set of rewriting rules) that vastly approximates English syntax for some ...
ChomskyEnjoyer's user avatar
1 vote
1 answer
114 views

What language does S -> A generates?

I read formal grammar's definition from Wikipedia, and it seems like there can be such a grammar like: S -> A //no more rules S and A are both non-terminals. What language does it generates? I've ...
kjh6b6a68's user avatar
  • 129
2 votes
0 answers
69 views

*Compact* Context-Free Grammar for English

I have seen that similar questions have been asked here, but the common answer is to look at Generalized Phrase Structure Grammar. Then, on the internet I just find slides from computational ...
a_gdevr's user avatar
  • 44
2 votes
1 answer
92 views

Is English modeled as a deterministic CFL or a CFL?

Books on linguistics and NLP often mention that English is modeled by context free grammars, but also is parsed by LR(k) parsers. LR(k) parsers are for parsing deterministic CFLs, while CFLs are ...
Tim's user avatar
  • 837
2 votes
2 answers
113 views

Can CFG (context free phrase structure grammar) describe discontinuous constituents?

If you google search "discontinuous constituent", you will see that various extensions to CFG have been proposed to describe discontinuous constituents. One of them is found in my favorite book on ...
Greg Lee's user avatar
  • 12.4k
0 votes
3 answers
244 views

Natural languages, programming languages, and information theory

The background The use of the context-free grammars in linguistics often prompts comparison with programming languages (e.g., see this question). Despite the formal structure similarities, I would ...
Roger V.'s user avatar
  • 970