The grammars tag has no wiki summary.
4
votes
3answers
87 views
Chomsky hierarchy for tree structures
I know of the Chomsky hierarchy, which concerns the expressive power of grammars to recognize languages $L \subseteq \Sigma^*$ made of words on an alphabet $\Sigma$.
Is there a similar hierarchy for ...
0
votes
2answers
155 views
Find minimum number of transformations to transform from input to target string
Given that I have an input string, for example: aab
And I am given a target string, for example: bababa
And then I am given a ...
1
vote
0answers
92 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 ...
7
votes
0answers
186 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 ...
6
votes
0answers
121 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 ...
-3
votes
1answer
366 views
Name for terminals on the left-hand side of grammar rules? [closed]
Consider rules as they are used for context-sensitive languages:
$\alpha A \beta \rightarrow \alpha \gamma \beta$
If $\alpha$ is always empty, we have right-context sensitive grammars:
$A \beta ...
0
votes
0answers
193 views
Determining if a grammar can be converted to LL(1)/LL(k) [closed]
I'd like to know if there is a way to determine if a context-free grammar can be converted to
a LL(1) grammar
a LL(k) grammar, whatever the value of k (so the algorithm should give the value of k)
...
1
vote
2answers
254 views
are there fixed context sensitive grammars which are PSPACE complete?
wikipedia entry says without reference that
"There are even some context-sensitive grammars whose fixed grammar recognition problem is PSPACE-complete."
This is stronger than saying that CSG is ...
4
votes
1answer
146 views
Contract preservation using grammars
I am exploring using annotated grammars to formalize and enforce parts of contracts between nodes in a distributed application.
I've found a number of articles on languages for specifying fairly ...
0
votes
1answer
148 views
Decide if a given sequence is regular or context-free
Given a sequence s (or a finite set of sequences) I would like to know if this was generated by a regular or by a context-free (supposes these are the only options) grammar.
Of course, this is an ...
9
votes
3answers
445 views
1-way Quantum Finite Automata Example Question
I'm attempting to clarify my understanding in the example presented in Section 2.2 of 1-way Quantum Finite Automata: Strengths Weaknesses and Generalizations (this alternative link may also be ...
2
votes
1answer
94 views
Is state splitting the LR equivalent of LL nonterminal replication
The grammar classes SLR and strong LL are similar in that they both use FOLLOW sets to resolve conflicts. For still unresolved conflicts, state splitting always works for SLR grammars, if the grammar ...
-1
votes
1answer
2k views
When converting a Context-Free Grammar to Chomsky Normal Form why is a new start state added? [closed]
I'm taking a theoretical computer science class and we just went over the steps to rewrite a context-free grammar in Chomsky Normal Form. The steps we were told to complete are:
Add a new start ...
0
votes
0answers
136 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 ...
-6
votes
1answer
1k views
How do you convert the following ambiguous grammar to unambiguous? [closed]
I understand how the difference between the two, how ambiguity means that there is at least one string with 2 distinct parse trees while there is only one in an unambiguous tree. But I can't seem to ...
2
votes
0answers
113 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.
...
0
votes
1answer
111 views
Lengths and substitution in L-systems
Am looking into writing up a Lindenmayer systems implementation. I've looked at a few example implementations and the one thing that's giving me trouble at this stage is how symbols and substitutions ...
0
votes
1answer
134 views
Describing a grammar and associated parser
In the process of writing a Turing machine simulator, I decided on a machine representation in ASCII that closely mirrors Turing's original machine tables. I am interested in the formal categorization ...
-1
votes
1answer
265 views
Generating a language from a given grammar
So I'm looking for a way of generating all words in language specified by a specific grammar and a alphabet. Is there an easy way to do this? The grammar is a stochastic context free grammar? Is there ...
17
votes
3answers
2k views
Proof of the pumping lemma for context-free languages using pushdown automata
The pumping lemma for regular languages can be proved by considering a finite state automaton which recognizes the language studied, picking a string with a length greater than its number of states, ...
5
votes
0answers
207 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, ...
2
votes
2answers
350 views
A formal grammar for P?
Let $P$ be the class of formal languages that have polynomial-time decider, i.e. for each $L\in P$ there exists a Turing-machine $T$ such that for each $w\in L$ machine $T$ decides if $w\in L$ in ...
-3
votes
2answers
626 views
Determine if a LL(2) grammar is strong
Given a LL(2) grammar , how can i determine if it is strong ?
10
votes
5answers
682 views
Which models of computation can be expressed through grammars?
This is a reformulation of Are grammars programs? previous asked by Vag and with many suggestions from the commenters.
In what way can a grammar be seen as specifying a model of computation?
If, for ...
1
vote
0answers
141 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 ...
10
votes
1answer
418 views
Closure of unambiguous context-free languages under pre- and postfix.
Let $L$ be a context-free language. Define $ppc(L)$ to be the pre- and postfix closure of $L$, in other words, $ppc(L)$ contains all of $L$'s prefixes and postfixes, and hence $L$ itself. My question: ...
3
votes
2answers
483 views
Is there an example of a non context-sensitive language?
I know $CSL\subset UL$ can be demonstrated by reduction to the absurd, but I've been trying to find a language that is in Type 0 ($UL$) and not in Context-Sensitive Languages ($CSL$).
Is there any ...
11
votes
1answer
206 views
Lower bounds on the size of CFGs for specific finite languages
Consider the following natural question: Given a finite language $L$, what is the smallest context-free grammar generating $L$?
We can make the question more interesting by specifying a sequence of ...
7
votes
1answer
330 views
Do there exists polynomial size CFG that describe this finite language?
Do there exists permutations $\pi_1,\pi_2$ and polynomial size (in $|w|=n$) context free grammar that describe the finite language $\{w \pi_1(w) \pi_2(w)\}$ over alphabet $\{0,1\}$?
UPDATE: For one ...
1
vote
0answers
265 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 ...
5
votes
2answers
195 views
Partially Ordered CFG
I'm looking for work about partially ordered context-free grammars. I've found one paper, which seems to simplify the problem too much (in addition to some technical mistakes, as far as I can tell). ...
3
votes
1answer
358 views
Are variables in RHS of Chomsky Normal Form productions distinct?
I'm wondering if it is permitted for production rules in a context-free grammar (CFG) in Chomsky Normal Form (CNF) to have multiple occurences of the same variable in the right-hand side of the ...
0
votes
0answers
645 views
Pumping Lemma with Context Free Languages [closed]
I have the language {a^i b^j c^k | i,j,k>=0 & i>j & j>k}
I began by assuming some m is picked for me, such that ...
18
votes
4answers
2k views
What is the most powerful kind of parser?
As a side-project, I'm writing a language using Python. I started by using a flex/bison clone called Ply, but am coming up against the edges in the power of what I can express with that style of ...
8
votes
1answer
330 views
Tool for translating PDAs to CFGs
We know that all push down automata are representable using context-free grammars. Furthermore, there is an algorithm to construct a CFG from any PDA (e.g. Sipser's proof in intro to theory of ...
5
votes
2answers
241 views
Why may the right hand sides in Chomsky Hierachy type 1 be larger?
I'm shaking my head because of this question, my Prof. didn't explain it. We have linear space limited automata and they have to satisfy for rules a -> b that |a| <= |b|.
Why?
I would have said, ...
24
votes
2answers
1k views
Is {$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} non-context-free?
Is the language {$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} context-free or not?
I realized that I have encountered almost all variants of this question with different conditions about the ...
