Skip to main content

Questions tagged [grammars]

The tag has no usage guidance.

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

Modify DCFG to enforce length limit

Given a deterministic context-free grammar $G$ that generates the language $L$, is there an efficient algorithm that can be used to construct another DCFG $G_N$ that generates the language $\{ s \in L ...
Jerry Ding's user avatar
0 votes
1 answer
86 views

What is the intution on the TTT algorithm for regular grammar inference?

This question is about the TTT algorithm for blackbox automata inference as defined in [1] and [2]. I am finding it difficult to understand all the innovations made by the algorithm. I understand how ...
Rahul Gopinath's user avatar
-1 votes
1 answer
84 views

Generating grammar from a string

Given a string generated with a valid grammar, how can I find list of all the valid grammar for that particular string? Problem statement - I'm trying to build a code base scanner, and I'd like to ...
Vetrivel's user avatar
0 votes
0 answers
68 views

How to reduce a code down to its configuration

I have built a system where from atomic information of a UI code I could generate a framework specific code. Here is the concept https://github.com/imvetri/ui-editor. For example, the user of this ...
Vetrivel's user avatar
0 votes
0 answers
30 views

Grammal formal doubt. Context-sensitive grammar

In the formal grammar context I am getting confused about the sensitive-context grammars. For this language: Looking for it in several sites, I found 2 different sensitive-context grammars which can ...
user69507's user avatar
0 votes
0 answers
75 views

Are there data structures that cannot be serialized / deserialized using a context free grammar?

I understand that deserializing data from a string or binary stream into a data structure is effectively the same parsing. When you deserialize the input string, you use a grammar to create a parse ...
bcarlborg's user avatar
1 vote
1 answer
234 views

Can an unrestricted grammar have a rule with only terminals on the left-hand side?

In the definition of unrestricted (type 0) grammars we only really have the rule that the lhs cannot be the empty string. Then, is it allowed to have a production rule with an lhs consisting only of ...
throwaway-grammars's user avatar
4 votes
1 answer
180 views

Subset of regular languages

I have a system that is deciding a subset of regular languages and am curious if anyone has seen this type before and if it has a name I could use to research more. Specifically consider the ...
sligocki's user avatar
  • 302
4 votes
1 answer
102 views

Is there any context-free language that is inherently ambiguous as an indexed language

Indexed languages are defined as being produced by indexed grammar. Is there any context-free language that is inherently ambiguous as an indexed language? That is, is there a context-free language ...
WangAtChicago's user avatar
5 votes
1 answer
108 views

Is there any inherently ambiguous indexed language?

Indexed languages are defined as being produced by an indexed grammar. My question is: Is there an indexed language such that there is no indexed grammar that can produce every word of the language in ...
WangAtChicago's user avatar
10 votes
0 answers
250 views

Smallest context-free grammar for powers of two summing to $2^k$

Let $k > 0$ and define an alphabet $\Sigma_k = \{ 2^0, 2^1, \ldots, 2^k \}$. Define: $$P_k = \{ a_1a_2\cdots a_t \in \Sigma_k^* \mid \sum_i a_i = 2^k \}.$$ This is a finite language. Question: Is ...
Michaël Cadilhac's user avatar
1 vote
0 answers
161 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 ...
Ondřej Guth's user avatar
5 votes
1 answer
173 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 ...
William Turner's user avatar
2 votes
1 answer
173 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. ...
user16237393's user avatar
5 votes
0 answers
98 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 ...
naloa's user avatar
  • 61
5 votes
1 answer
146 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 ...
DG_'s user avatar
  • 411
2 votes
0 answers
26 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 ...
botsina's user avatar
  • 101
3 votes
0 answers
157 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 ...
Joshua Wise's 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 ...
Novicegrammer's user avatar
6 votes
3 answers
449 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 ...
Novicegrammer's user avatar
-1 votes
1 answer
174 views

Ordered Grammar in THEORY OF COMPUTATION [closed]

What is ordered grammar in the theory of computation?
Raj Aryan Pathak's user avatar
2 votes
0 answers
73 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 ...
Alex W's user avatar
  • 121
3 votes
1 answer
159 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, ...
Joey Eremondi's user avatar
3 votes
1 answer
166 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 ...
Martin Berger's user avatar
0 votes
1 answer
120 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)...
Djaouad's user avatar
  • 119
4 votes
2 answers
172 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 ...
Rahul Gopinath's user avatar
14 votes
4 answers
649 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 ...
DG_'s user avatar
  • 411
6 votes
0 answers
105 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 ...
Kaban-5's user avatar
  • 245
6 votes
1 answer
167 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 (...
Andrey Lebedev's user avatar
1 vote
0 answers
67 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-...
CinchBlue's user avatar
  • 309
4 votes
1 answer
1k 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 ...
Niteraleph's 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
460 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$...
Andrey Lebedev's user avatar
6 votes
1 answer
2k 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 ...
Michael Wehar's user avatar
3 votes
1 answer
163 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 ...
Andrey Lebedev's 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 ...
Franki's user avatar
  • 189
5 votes
0 answers
163 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)$ ...
Andrey Lebedev's 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 ...
Andrey Lebedev's user avatar
13 votes
3 answers
5k 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 ...
CinchBlue's user avatar
  • 309
1 vote
2 answers
120 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,...
sean's user avatar
  • 722
1 vote
0 answers
201 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 ...
nanogru's 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 ...
Jára Cimrman's user avatar
1 vote
0 answers
117 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 ...
StefanH's user avatar
  • 2,077
4 votes
1 answer
114 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 ...
Andrey Lebedev's user avatar
5 votes
1 answer
150 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\...
Andrey Lebedev's user avatar
3 votes
0 answers
96 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 ...
Andrey Lebedev's user avatar
8 votes
2 answers
386 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 ...
Andrey Lebedev's user avatar
3 votes
0 answers
177 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 ...
Andrey Lebedev's user avatar
6 votes
2 answers
389 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)$ ...
Shahab's user avatar
  • 338
10 votes
1 answer
550 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 ...
Christian Hagemeier's user avatar