Questions tagged [grammars]
The grammars tag has no usage guidance.
106
questions
-1
votes
1
answer
71
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 ...
- 99
0
votes
0
answers
62
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 ...
- 99
0
votes
0
answers
29
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 ...
0
votes
0
answers
62
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 ...
1
vote
1
answer
144
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 ...
3
votes
1
answer
165
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 ...
- 292
4
votes
1
answer
96
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 ...
- 101
5
votes
1
answer
106
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 ...
- 101
10
votes
0
answers
248
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 ...
- 3,946
1
vote
0
answers
159
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 ...
- 11
5
votes
1
answer
171
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 ...
2
votes
1
answer
170
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.
...
- 21
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 ...
- 61
5
votes
1
answer
145
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 ...
- 411
2
votes
0
answers
24
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 ...
- 101
3
votes
0
answers
146
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 ...
- 131
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 ...
- 173
5
votes
3
answers
422
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 ...
- 173
-1
votes
1
answer
155
views
Ordered Grammar in THEORY OF COMPUTATION [closed]
What is ordered grammar in the theory of computation?
2
votes
0
answers
69
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 ...
- 121
3
votes
1
answer
152
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,830
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 ...
- 11.4k
0
votes
1
answer
110
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)...
- 119
4
votes
2
answers
152
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 ...
- 175
14
votes
4
answers
618
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 ...
- 411
6
votes
0
answers
98
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 ...
- 245
6
votes
1
answer
165
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 (...
- 635
1
vote
0
answers
65
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-...
- 309
4
votes
1
answer
950
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 ...
- 53
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 ...
user37129
4
votes
1
answer
443
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$...
- 635
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 ...
- 5,127
3
votes
1
answer
150
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 ...
- 635
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 ...
- 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)$ ...
- 635
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 ...
- 635
13
votes
3
answers
4k
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 ...
- 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,...
- 722
1
vote
0
answers
187
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 ...
- 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 ...
- 464
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 ...
- 2,037
4
votes
1
answer
112
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 ...
- 635
5
votes
1
answer
148
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\...
- 635
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 ...
- 635
8
votes
2
answers
383
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 ...
- 635
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 ...
- 635
6
votes
2
answers
381
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)$ ...
- 338
10
votes
1
answer
518
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
2
answers
285
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
...
- 635
7
votes
0
answers
795
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 ...
- 420