Questions tagged [grammars]

The tag has no usage guidance.

29 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
13
votes
0answers
1k views

Is CFL strictly contained in NL?

We know that $\mathsf{REG}=\mathsf{NSPACE}(O(1))$ and $\mathsf{CSL}=\mathsf{NSPACE}(O(n))$. What is the relation of $\mathsf{CFL}$ and $\mathsf{NSPACE}(O(\log n))=\mathsf{NL}$? Is $\mathsf{CFL}$ a ...
9
votes
0answers
241 views

Complexity of a problem over acyclic context-free grammars

Let $G$ be an acyclic, context-free grammar over a fixed alphabet $\Sigma=\{a_1,\dots,a_k\}$ with the restriction (without loss of generality) that $|w|=2$ for each rule $A\to w$ in the grammar. ...
7
votes
0answers
892 views

Names for the left- and right-hand sides of a grammar production?

Problem I'm writing a document where I have to describe some of the properties of a type system as they relate to a particular formal grammar. I was trying to refer to the right-hand-sides of the ...
7
votes
0answers
335 views

The semantics of Parsing Expression Grammars

Is there a simple and intuitive explanation for the fact that the following parsing expression (where S is the starting symbol, $...
6
votes
0answers
87 views

Reference request: transforming a grammar to Greibach normal form preserves the number of parse trees

I believe that most "natural" ways of transforming a grammar to the GNF should preserve the number of parse trees for each string. For example, Urbanek's construction from the paper "On Greibach ...
6
votes
0answers
641 views

Does PEG contain CFG?

Despite their considerable expressive power, all PEGs can be parsed in linear time using a tabular or memoizing parser (8). These properties strongly suggest that CFGs and PEGs define incomparable ...
5
votes
0answers
161 views

“Context” understanding in tree grammars

The Context-Free tree grammar has rules of the form: $A\rightarrow t$ or $A(x_1,\dots,x_n)\rightarrow t_x$, where $A\in N$, $t\in T(N\cup T)$, $t_x\in T(N\cup T\cup \{x_1,\dots,x_n\})$, $T(Z)$ ...
5
votes
0answers
112 views

Word grammars with free variables

I am trying to find any described formalism which introduces free variables into word grammars (I emphasize here word in order not to be confused with very similar thing in tree grammars). What I ...
3
votes
0answers
66 views

Useful notion of ambiguous growing context-sensitive language

As far as I understand there is no useful notion of ambiguous context-sensitive language. For example for any inherently ambiguous context-free language there is a context-sensitive grammar generating ...
3
votes
0answers
66 views

Deciding whether an arbitrary context-free grammar generates a deterministic push-down automata?

I know that it's undecidable whether an arbitrary context-free grammar is ambiguous, but is it decidable whether that grammar is deterministic? I can't find the answer to this question anywhere on the ...
3
votes
0answers
91 views

Grammar with “dead” derivation chains

This question is inspired by the great answer given by Jeffrey Shallit on my question about proper CSG for $a^n b^n c^n$ language. Disclaimer:: I'm not arguing about correctness of this grammar. This ...
3
votes
0answers
168 views

Context-Sensitive Grammar characteristic properties

This question can look like some kind of puzzle, but it is actually part of more complex applied problem. Let's consider subspace of Context-Sensitive Grammars, which contains grammars which can not ...
3
votes
0answers
120 views

minimal languages that “cover” grammar productions

this question is based on generalizing two somewhat similar questions that recently appeared on the "sister" beta site cs.se (now with more questions than this one!) and which seems theoretically ...
3
votes
0answers
228 views

Learning about Nested Stack Automata

I want to learn about nested stack automata. However my efforts to find a suitable learning resource have so far been abortive: The Wikipedia article on nested stack automata is a stub. Alfred Aho's ...
2
votes
0answers
15 views

Power of Hyperedge Replacement Grammars (HRGs)

Can HRGs generate languages which equal or include the following graph languages: All (bipartite) graphs of bounded degree All (bipartite) planar graphs of bounded degree All (bipartite) planar ...
2
votes
0answers
54 views

A Context-Sensitive Grammar which cannot be recognised by a Parsing Expression Grammar

It is (currently) an open question of whether every context-free grammar can be recognised by some parsing expression grammar. [1] However, has it been proven that there exists an example of a ...
2
votes
0answers
108 views

Notion of “quotient” or “inverse” for recognizable tree languages?

Related to my previous question but this time I have a better idea of what I'm actually asking. I'm looking at the following operation on recognizable tree languages (i.e. regular tree grammars, ...
2
votes
0answers
36 views

A class of languages admitted by a class of grammars equivalent to $\mathbf{PR}$?

Is there a class of languages $L(G)$ admitted by a class of phrase structure grammars $G$ equivalent to $\mathbf{PR}$? (the class of primitive recursive languages = $\mathbf{LOOP}$)? In greater ...
2
votes
0answers
232 views

Structural equivalence of two context-free grammars

I understand that determining if two context-free grammars are structurally equivalent is decidable (according to the 1968 paper by Paull, M.C. and Unger, S.H., "Structural equivalence of context-free ...
2
votes
0answers
123 views

Ref request: grammar specification how-to

I am looking for a reference where I can learn a reasonably systematic approach to how to specify a formal grammar for a given syntax. By a "formal grammar" I mean something like a BNF description. (...
1
vote
0answers
58 views

What is the interpretation of an infinite formal context-free grammar?

Let $L$ be a language as follows: $$ \begin{align*} L &::= a\ |\ L^{*}\\ \end{align*} $$ Now, suppose I apply some sort of transformation $T : N \rightarrow N$ where $N$ is the set of non-...
1
vote
0answers
117 views

Relation between MDPs and non-deterministic finite automatons

I'm confused as to the relation (computability-wise) between markov decision processes and NFAs. Are finite state MDPs expressible as regular grammars? If so, are markov decision processes thus ...
1
vote
0answers
106 views

If for every non-terminal in a cs-grammar there exists an obligatory rule, does this alter the language of derivable strings

I am reading Chomsky's article Three models for the description of language, one of the earliest papers where context-free and context-sensitive grammars are mentioned. Essentially what he calls ...
1
vote
0answers
39 views

Determine whether a categorical grammar is minimal concerning lexical entries

In order to compare the descriptional complexity of context-free and (combinatoric) categorical I need a way to check if a categorical grammar of a formal language is minimal concerning lexical ...
1
vote
0answers
198 views

LALR grammars subsets

If LR(0) condition for a grammar G is formulated as follows: Every state is either reduction or a shift state and it can't be both at the same time if it is a reduction state, it contains exactly one ...
1
vote
0answers
315 views

Restricted read twice BDDs and context free grammars

Several papers give poly-time algorithms for constrained paths on labelled graphs, e.g. [1] Quote: Given an alphabet Σ, a (directed) graph G whose edges are weighted and Σ-labeled, and a formal ...
0
votes
0answers
20 views

Given two languages and their grammars can you translate from one to the other?

Often I use sed 's/match/replacement/' in places where I would rather have a more formal tool, just because sed is what I know. ...
0
votes
0answers
39 views

Self Generating Grammars - Does it have to be infinite recursion?

For brevity, let's redefine a grammar to be just the three-tuple $(\Sigma_G, P_G, S_G)$. As usual, $\Sigma_G$ is the alphabet, $P_G$ are the production rules and $S_G$ is the start rule of $G$. For ...
0
votes
0answers
176 views

Classification of Saturated LL(1) Grammars

By saturated I mean that the grammar accepts every possible string that can be constructed from the terminal set. So the parse table would be full of valid entries, no error entries at all. Can such a ...