The tag has no usage guidance.

learn more… | top users | synonyms

6
votes
1answer
158 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
89 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, ...
4
votes
0answers
141 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. ...
3
votes
0answers
46 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, ...
4
votes
0answers
74 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
220 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 ...
4
votes
1answer
123 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 ...
0
votes
1answer
102 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, ...
4
votes
1answer
50 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
128 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 ...
5
votes
2answers
269 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 ...
5
votes
1answer
142 views

What is the importance of linear languages?

What is the point of linear languages? They appear to be an intermediate set of languages in between regular and context-free languages, but do they have any useful or nice properties that either have ...
3
votes
0answers
83 views

minimal languages that “cover” grammar productions

this question is based on generalizing two somewhat similar questions that recently appeared on the "sister" beta site cs.se (now with more questions than this one!) and which seems theoretically ...
4
votes
1answer
226 views

What characterizations exist for the grammars that can express subsets of the context-free languages?

It is well known that CFGs and PDAs are equivalent, and there has been extensive research about the relationship between deterministic pushdowns and $LR(1)$ grammars, as $DCFL$ is a subset of $LR(1)$. ...
8
votes
1answer
140 views

Asymptotic density of ambiguous context-free grammars (CFGs)

What is the ratio of ambiguous CFGs to all CFGs? Since both sets are countably infinite the ratio is not well-defined. But what about the asymptotic density: $$\lim_{n \mapsto \infty}\frac {\# ...
4
votes
1answer
723 views

What are the relationship and difference between ambiguous grammars and non-deterministic ones?

Intuitively, I had assumed that ambiguous grammars were roughly the same as non-deterministic grammars. According to Wikipedia however, this is false: there are non-deterministic unambiguous CFGs ...
2
votes
1answer
63 views

Define the properties of a grammar that is the fastest to parse

It's possible to define the properties of a grammar that is fast to parse as it is indeed possible to classify algorithm based on their complexity ? In other words it's possible to evaluate and ...
1
vote
1answer
199 views

How can an inherited attribute be simulated using a synthesized attribute?

Is it possible to simulate an inherited attribute using a synthesized attribute? For example, can the inherited attribute SYMTAB used in normal code generation modules be simulated using a synthesized ...
0
votes
1answer
256 views

Has anyone mixed linear algebra with formal language theory in this way?

Let $G$ be the grammar: $$ S \rightarrow aAb \\ A \rightarrow aA + a + \epsilon $$ where $\epsilon$ is the empty string, $a,b$ are terminals and $S,A$ non-terminals with $S$ the start symbol. ...
1
vote
0answers
31 views

Determine whether a categorical grammar is minimal concerning lexical entries

In order to compare the descriptional complexity of context-free and (combinatoric) categorical I need a way to check if a categorical grammar of a formal language is minimal concerning lexical ...
1
vote
0answers
139 views

Learning about Nested Stack Automata

I want to learn about nested stack automata. However my efforts to find a suitable learning resource have so far been abortive: The Wikipedia article on nested stack automata is a stub. Alfred Aho's ...
1
vote
1answer
459 views

Difference between a cyclic and a left-recursive context-free grammar?

I am currently reading a paper indicating that a cyclic CFG and a left-recursive CFG are different things: The original purpose of the LC transform is to allow simulation of left-corner parsing ...
6
votes
3answers
320 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 ...
1
vote
2answers
261 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
188 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 ...
9
votes
0answers
375 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
229 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
394 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 ...
1
vote
2answers
356 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
161 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
200 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 ...
8
votes
3answers
670 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
126 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
4k 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
168 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 ...
2
votes
0answers
118 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
139 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
161 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
562 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 ...
18
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, ...
7
votes
0answers
292 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
377 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 ...
-2
votes
2answers
1k views

Determine if a LL(2) grammar is strong

Given a LL(2) grammar , how can i determine if it is strong ?
17
votes
6answers
914 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
163 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
544 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: ...
4
votes
2answers
989 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 ...
13
votes
1answer
291 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 ...
8
votes
1answer
536 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
296 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 ...