Questions tagged [grammars]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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. ...
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 ...
5
votes
1answer
124 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 ...
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 ...
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 ...
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 ...
4
votes
3answers
306 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 ...
-1
votes
1answer
107 views

Ordered Grammar in THEORY OF COMPUTATION [closed]

What is ordered grammar in the theory of computation?
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, ...
3
votes
1answer
138 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 ...
0
votes
1answer
93 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)...
4
votes
1answer
97 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 ...
14
votes
4answers
596 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 ...
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
1answer
152 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 (...
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-...
4
votes
1answer
701 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 ...
3
votes
1answer
58 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 ...
3
votes
1answer
326 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$...
5
votes
1answer
975 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 ...
3
votes
1answer
80 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 ...
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 ...
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 ...
13
votes
3answers
2k 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 ...
1
vote
2answers
117 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,...
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 ...
19
votes
1answer
957 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 ...
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 ...
3
votes
1answer
106 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 ...
5
votes
1answer
139 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\...
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 ...
8
votes
2answers
345 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 ...
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 ...
6
votes
2answers
293 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)$ ...
9
votes
1answer
409 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 ...
6
votes
2answers
255 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 ...
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 ...
7
votes
1answer
231 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 $(...
4
votes
1answer
102 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, ...
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. ...
6
votes
1answer
289 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, ...
5
votes
1answer
496 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 ...
10
votes
1answer
310 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 ...
5
votes
1answer
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 ...
1
vote
1answer
634 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, ...
9
votes
2answers
177 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 ...
7
votes
1answer
167 views

Is $LL(k)$ for large $k$ considered harmful? If so, why?

I took a course touching on lexer and parser theory this semester (a sizeable chunk was devoted to regexes and other FSA, but context-free grammars were covered as well). Over the course of the ...
6
votes
2answers
380 views

Which factors make the problem of inferring the grammar difficult?

Scott Aaronson said in the paper entitled "Why Philosophers Should Care About Computational Complexity" (Please see ECCC Report: TR11-108, section 7, pp 25-31): Following the work of Kearns and ...