# Tagged Questions

The tag has no usage guidance.

78 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 ...
117 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 ...
67 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 ...
173 views

177 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. ...
63 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, ...
93 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 ...
227 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 ...
193 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 ...
140 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, ...
54 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 ...
138 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 ...
286 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 ...
147 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 ...
87 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 ...
232 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)$. ...
145 views

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 ...
145 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 ...
541 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 ...
334 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 ...
269 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 ...
195 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 ...
456 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 ...
246 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 ...
397 views

378 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 ...
1k views

### Determine if a LL(2) grammar is strong

Given a LL(2) grammar , how can i determine if it is strong ?
930 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 ...
164 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 ...
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: ...
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 ...