Questions tagged [grammars]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
82 views

Can we describe any context-sensitive language by a grammar without left recursion?

The main question: is it possible to avoid left recursion in a context-sensitive grammar (see example below), i.e., if for any context-sensitive language $L$, there exists some context-sensitive ...
user avatar
5 votes
1 answer
153 views

Alternative to LBA for recognising context-sensitive languages

I've always felt that there's no "canonical" automata for recognising context-sensitive languages. Much like there's DFA for regular, PDA for context-free and Turing machines for RE. I'm ...
user avatar
2 votes
1 answer
156 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. ...
user avatar
3 votes
0 answers
81 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 ...
user avatar
  • 41
5 votes
1 answer
133 views

Different definitions of grammar complexity

It's known that there are different "kinds" of grammar complexity of language $L$ --- nonterminal complexity (minimal possible $|N|$ for grammar $(N, \Sigma, P, S)$ generating $L$), covering ...
user avatar
  • 411
2 votes
0 answers
17 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 ...
user avatar
  • 101
3 votes
0 answers
100 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 ...
user avatar
0 votes
0 answers
40 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 ...
user avatar
5 votes
3 answers
355 views

Why do people bring real-life Quantum Computing to the discussion of the Church-Turing thesis?

As an undergraduate with limited understanding of QC and even the C-T thesis, I have problems figuring out why in questions such as Extended Church-Turing Thesis real-life quantum stuff is even given ...
user avatar
-1 votes
1 answer
123 views

Ordered Grammar in THEORY OF COMPUTATION [closed]

What is ordered grammar in the theory of computation?
user avatar
2 votes
0 answers
61 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 ...
user avatar
  • 121
2 votes
0 answers
115 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, ...
user avatar
3 votes
1 answer
149 views

Compressing grammars by introducing ambiguity and left-recursion

This is a reference request. What is known about the following questions? Problem: Given a grammar $G$ (for example context-free) with language $L$ we can introduce a new grammar $G'$ which also ...
user avatar
0 votes
1 answer
96 views

Why can't a left-recursive, non-deterministic, or ambiguous grammar be LL(1)?

I've learned from several sources that an LL(1) grammar is: unambiguous, not left-recursive, and, deterministic (left-factorized). What I can't fully understand is why the above is true for any LL(1)...
user avatar
  • 119
4 votes
1 answer
106 views

What is the current state of the art in black-box grammar induction?

Grammar induction of Context Free Languages seems to be a very well researched field. I would like to know the current state of the art in inducing a Context Free Grammar (I am reading up Higuera's ...
user avatar
14 votes
4 answers
609 views

Base-k representations of the co-domain of a polynomial - is it context-free?

In chapter 4 of Jeffrey Shallit's A Second Course in Automata Theory the following problem is listed as open: Let $p(n)$ be a polynomial with rational coefficients such that $p(n) \in \mathbb{N}$ for ...
user avatar
  • 411
6 votes
0 answers
90 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 ...
user avatar
  • 245
6 votes
1 answer
162 views

Example of context-free tree language which can not be generated by monadic CFTG

Assuming that a context-free tree language (CFTL) is that which is generated by a context-free tree grammar (CFTG), I am looking for an example of CFTL which can not be generated by a monadic CFTG (...
user avatar
1 vote
0 answers
62 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-...
user avatar
  • 309
4 votes
1 answer
828 views

How to start learning formal language theory

I sincerely apologize if this is not appropriate in this stack Q&A, though it seemed the most fitting. I want to learn formal language theory, as well as generating grammars etc. The purpose is ...
user avatar
3 votes
1 answer
59 views

Relation between OSAs and grammars

Are there any relation between order-sorted algebra (OSA) and grammars (context-free grammar in particular)? If I'm not mistaken, according to [1], there is an equivalence between order-sorted and ...
user avatar
4 votes
1 answer
382 views

Converting Kuroda normal form rules to the Penttonen normal form

Let us say we have some abstract context-sensitive grammar in the Kuroda normal form, which is where all production rules are of the form: $AB\rightarrow CD$ or $A\rightarrow BC$ or $A\rightarrow B$...
user avatar
5 votes
1 answer
1k views

What is the complexity of counting parse trees?

A Counting Problem Given a CFG $G$ and a string $s$, how many distinct parse trees are there for the string $s$? An Example Instance Let's consider an example instance consisting of a CFG $G$ with ...
user avatar
3 votes
1 answer
117 views

Looking for a particular normal form for Context-sensitive grammar

I am wondering if there is a described normal form for Context-sensitive grammar, which is something similar to Kuroda normal form and Greibach normal form. That is to say, each rule in such form ...
user avatar
2 votes
0 answers
40 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 ...
user avatar
  • 89
5 votes
0 answers
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)$ ...
user avatar
5 votes
0 answers
114 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 ...
user avatar
13 votes
3 answers
3k views

What are graph grammars?

I have found information on graph grammars and graph rewriting, but the papers that I find on it are a bit thick. Can someone give a quick overview of what graph grammars are, as well as an overview ...
user avatar
  • 309
1 vote
2 answers
118 views

Determine if a structure is a model of an inductively defined predicate

My setting is first-order logic. As an example, consider an inductive definition of a linked list: $List(l)$ = $Null(l)$ $\vee~(Node(l) \wedge \exists sublist. List(sublist) \wedge next(l,...
user avatar
  • 702
1 vote
0 answers
141 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 ...
user avatar
  • 121
19 votes
1 answer
1k views

Is equivalence of unambiguous context-free languages decidable?

It is well known that the equivalence problem is undecidable for general context-free languages. However, all proofs of this fact that I am aware of seem to involve some ambiguous context-free ...
user avatar
1 vote
0 answers
114 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 ...
user avatar
  • 1,947
4 votes
1 answer
109 views

Place of tree-adjoining grammars in the hierarchy of tree grammars

As tree-adjoining grammars operate with trees, I suppose they can be considered as a kind of tree grammars. If this assumption is correct, I'm wondering: where should we place them in the tree grammar ...
user avatar
5 votes
1 answer
142 views

Regarding proper form of production rules of Context-free tree grammars

Is it possible to describe Context-free Tree Grammar $G_t$ such that set of yields of its trees will coincide with Context-sensitive word language $a^nb^nc^n$? $\{a^nb^nc^n | n>0\}=\{Yield(t)|t\...
user avatar
3 votes
0 answers
94 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 ...
user avatar
8 votes
2 answers
369 views

Mistake in Wikipedia CSG example?

I'm confused about the example given in Wikipedia article about Context-sensitive grammar: https://en.wikipedia.org/wiki/Context-sensitive_grammar Disclamer: I've already changed discussed section ...
user avatar
3 votes
0 answers
175 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 ...
user avatar
6 votes
2 answers
331 views

Finding smallest context free grammar that generates a set of sets

Are there any results known about the size of smallest context free grammar that generates a set of sets? That is, I am given an alphabet $\Sigma$ as well as a set $S \subseteq \mathbb{P}(\Sigma)$ ...
user avatar
  • 338
10 votes
1 answer
454 views

Chomsky Schützenberger enumeration theorem

In many textbooks the Chomsky-Schützenberger enumeration theorem is stated as that the characteristic formal power series of a language is $\mathbb N$-algebraic, if the grammar is unambigious. In some ...
user avatar
6 votes
2 answers
274 views

Known and described subclasses of Context-Free Grammars class

I'm looking for various researches which consider specific subclasses of Context-Free Grammar class, i.e. some specific described cases, which differ from well-known: deterministic/non-deterministic ...
user avatar
7 votes
0 answers
725 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 ...
user avatar
7 votes
1 answer
241 views

Complexity of a graph-rewriting problem

I recently came across the following problem which seems to fall in the context of graph rewriting problems: Input: A graph $G=(V,E)$ with maximum degree 3, an edge $e_0 \in E$ and pairs of graphs $(...
user avatar
  • 607
4 votes
1 answer
104 views

Which kind of grammar is the following?

Let me define the following "grammar": $$A_0 \leftarrow 1$$ $$A_{i+1} \leftarrow A_i \mid A_i \ K_{i+1} \mid A_i \ K_{i+1} \ A_i$$ where $1$ and $K_i$ are terminals (infinite amount of them: $K_1, ...
user avatar
9 votes
0 answers
253 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. ...
user avatar
  • 490
6 votes
1 answer
362 views

Counting words of length $n$ in an inherently ambiguous CFG?

There is a polynomial-time algorithm for computing the number of words of length $n$ in an unambiguous CFG $G = (V, \Sigma, R, S)$ (via a dynamic programming approach). However, for ambiguous CFGs, ...
user avatar
  • 545
5 votes
1 answer
525 views

Parse structure of a range concatenation grammar (RCG)

I know that with a context-free grammar, one can represent the results of a parse as a parse-tree. Specifically, each node represents one application of a production rule, is usually named for the LHS ...
user avatar
  • 605
10 votes
1 answer
330 views

What is the state complexity of the copy language?

Let a number $n$ be given. Consider the following language $L_n = \{ \; ww \; \vert \; w \in \{0,1\}^{n} \; \}$. In words, $L_n$ is the set of copy strings of length $2n$. Consider the following ...
user avatar
5 votes
1 answer
2k views

Emptiness of PDA without constructing the corresponding CFG

The emptiness problem for Context free Grammars(CFG) is well studied. The same holds for the equivalence problem between Pushdown Automata (PDA) and CFGs. Therefore, given a PDA, the straightforward ...
user avatar
  • 188
1 vote
1 answer
658 views

What is the grammar of network protocols and file formats?

For network protocols and/or file formats with fixed length fields, the grammar is fairly simple, and can be explained with a regular expression. However, for protocols with varying data lenghts, ...
user avatar
9 votes
2 answers
190 views

Is there higher-dimensional generative grammar?

I'm interested in computer music, where there are approaches to treat pieces of music as sentences in generative grammars or L-systems. Instead of composing, one could then specify a grammar and let ...
user avatar
  • 574