Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
15 votes
2 answers

Are the Before and After sets for context-free grammars always context-free?

Let $G$ be a context-free grammar. A string of terminals and nonterminals of $G$ is said to be a sentential form of $G$ if you can obtain it by applying productions of $G$ zero or more times to the ...
Alex ten Brink's user avatar
11 votes
2 answers

How can I prove this language is not context-free?

I have the following language $\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\}$ I am trying to determine which Chomsky language class it fits into. I can see how it could be made using a context-...
justausr's user avatar
  • 435
6 votes
1 answer

Can every linear grammar be converted to Greibach form?

Can every linear grammar be converted to a linear Greibach normal form, a form in which all productions look like $A \rightarrow ax$ where $a \in T$ and $x \in V \cup \{\lambda\}$? ($T$ is the set of ...
Gigili's user avatar
  • 2,193
10 votes
1 answer

Given a string and a CFG, what characters can follow the string (in the sentential forms of the CFG)?

Let $\Sigma$ be the set of terminal and $N$ the set of non-terminal symbols of some context-free grammar $G$. Say I have a string $a \in (\Sigma \cup N)^+$ such that $x a y \in \mathcal{S}(G)$ where $...
Thomas's user avatar
  • 203
17 votes
3 answers

Decidable non-context-sensitive languages

It is arguable that most languages created to describe everyday problems are context-sensitives. In the other hand, it is possible and not hard to find some languages that are not recursive or even ...
Victor Stafusa - BozoNaCadeia's user avatar
40 votes
2 answers

Are there inherently ambiguous and deterministic context-free languages?

Let us call a context-free language deterministic if and only if it can be accepted by a deterministic push-down automaton, and nondeterministic otherwise. Let us call a context-free language ...
Patrick87's user avatar
  • 12.8k
23 votes
1 answer

Is there any nongeneral CFG parsing algorithm that recognises EPAL?

EPAL, the language of even palindromes, is defined as the language generated by the following unambiguous context-free grammar: $S \rightarrow a a$ $S \rightarrow b b$ $S \rightarrow a S a$ $S \...
Alex ten Brink's user avatar
76 votes
1 answer

Language theoretic comparison of LL and LR grammars

People often say that LR(k) parsers are more powerful than LL(k) parsers. These statements are vague most of the time; in particular, should we compare the classes for a fixed $k$ or the union over ...
Raphael's user avatar
  • 72.3k
35 votes
9 answers

What is the significance of context-sensitive (Type 1) languages?

Seeing that in the Chomsky Hierarchy Type 3 languages can be recognised by a state machine with no external memory (i.e., a finite automaton), Type 2 by a state machine with a single stack (i.e. a ...
bitmask's user avatar
  • 1,755
7 votes
1 answer

How to convert a non-embedding context free grammar to regular grammar?

A context-free grammar is said to be self-embedding if and only if contains a derivation of the form $\xi\stackrel*\Rightarrow u\xi v$, where $\xi$ is a non-terminal and $u$, $v$ are some non-empty ...
user avatar

22 23 24 25