The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
61 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
72 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
198 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
127 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 {\# ...
3
votes
1answer
144 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 ...
0
votes
0answers
51 views

An algorithm for extracting grammars given existing grammar

Let all the grammars of concern here be CFGs. Let $A$ be a grammar with rules $A^i \Rightarrow a_1^i \dots a_{n_i}^i, \ i = 1 \dots n$, where each $a_i^j$ is either a terminal in $\Sigma$ or a rule ...
0
votes
0answers
29 views

Resolving ambiguity in an LALR grammar with empty productions

I'm working on an LALR grammar for a constrained Algol-ish kind of language. I'm having a problem with my Procedure definitions. I have the constraint that a Procedure is any number of variable ...
2
votes
1answer
51 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
127 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
201 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
27 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
113 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 ...
0
votes
1answer
251 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 ...
5
votes
3answers
260 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
228 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
139 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
233 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
169 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
386 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
317 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
156 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
182 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
562 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
117 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
3k 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
161 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
117 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
133 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
150 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
452 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
267 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
366 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
842 views

Determine if a LL(2) grammar is strong

Given a LL(2) grammar , how can i determine if it is strong ?
16
votes
6answers
834 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
155 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 ...
9
votes
1answer
500 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
615 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 ...
12
votes
1answer
246 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
421 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
287 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
218 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
419 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 ...
20
votes
4answers
3k 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
359 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
248 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, ...
28
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 ...