The tag has no usage guidance.

learn more… | top users | synonyms (1)

-6
votes
0answers
44 views

Is this a valid derivation? [on hold]

Salutations, I am currently studying CFGs at my Uni and am having some issues with understand the concept behind it (would help if the book 'Languages and Machines Ed. 3' wasn't soo god awful and if I ...
8
votes
0answers
65 views

Chomsky-Schützenberger for Deterministic CFLs

Is there a Chomsky-Schützenberger representation theorem for deterministic CFLs? Knowing precisely the class of morphisms under which DCFL is closed, such a theorem would probably be of the form: ...
11
votes
1answer
122 views

Are DPDAs without a $\epsilon$ moves as powerful as DPDAs with them?

In the formal description of Deterministic Pushdown Automata, they allow $\epsilon$ moves, where the machine can pop or push symbols onto the stack without reading a symbol from the input. If these ...
0
votes
2answers
65 views

Example of R and G when $R \subseteq L(G)$ is undecidable [closed]

Could anybody provide an example of regular language R and context-free grammar G such that $R \subseteq L(G)$ is undecidable. Of course, if such language could be constructed. Thanks.
8
votes
1answer
187 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 ...
0
votes
0answers
91 views

CSP-problem, based on context-free grammar

I'm trying to solve a CSP (Constraint-Satisfaction-Problem), which is based on arbitrary context-free grammars. A quick example: Let's say we have a context-free grammar with the following production ...
0
votes
1answer
104 views

Deciding whether a context-free language is regular [closed]

Does anyone know whether the following decision problem is decidable: Given a context-free language $L$, is $L$ regular? Here $L$ can be expressed, e.g., using a context-free grammar. Does anyone ...
2
votes
0answers
100 views

Decidability of CFG ambiguity

I have been trying to show the following language is undecidable. $L = \{ (\langle G \rangle , n ): G$ is a context-free grammar with an ambiguous string of length $\le n \}$. I think it is ...
9
votes
1answer
148 views

Membership problem for certain class of unrestricted grammars

Consider an arbitrary context-free grammar $G$ over the alphabet $\lbrace 0,1,\overline{0} ,\overline{1} \rbrace$. To the productions of this grammar, add two fixed non-context-free productions $P$: ...
0
votes
0answers
109 views

In what complexity classes other than $NP$ are these problems related to unary languages?

If I remember correctly saw this reduction in a paper can't find at the moment. Consider the following NP-complete variation of the Subset Sum problem. Given a set of positive integers ...
4
votes
1answer
220 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)$. ...
6
votes
2answers
127 views

Are deterministic context-free languages closed under outfix (or other erasing operations)

Define the outfix of a language $L$ to be $Outf(L) = \{xy \mid \exists z. xzy \in L \}$. Are any known results about whether deterministic context-free languages are closed under this operation, or ...
20
votes
3answers
318 views

Complexity of intersection of regular languages as context-free grammars

Given regular expressions $R_1, \dots, R_n$, are there any non-trivial bounds on the size of the smallest context-free grammar for $R_1 \cap \cdots \cap R_n$?
8
votes
1answer
139 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 {\# ...
0
votes
0answers
62 views

Which paper first showed that any context-free grammar (CFG) is equivalent to some CFG in Chomsky normal form?

Which paper first showed that any context-free grammar (CFG) is equivalent to some CFG in Chomsky normal form? I cannot find an reference.
-1
votes
1answer
140 views

is determining an unknown CFL from intersection of two CFLs decidable?

this problem was asked over a week ago on cs.se now with 7v and no answers so far, ie still "open". (there are many somewhat related problems/near variants re CFLs but its not obvious how to reduce it ...
12
votes
2answers
198 views

Reference for Dyck languages being $\mathsf{TC}_0$-complete

Dyck languages $\mathsf{Dyck}(k)$ is defined by the following grammar $$ S \rightarrow SS \,|\, (_1 S )_1 \,|\, \ldots \,|\, (_k S )_k \,|\, \epsilon $$ over the set of symbols ...
5
votes
1answer
190 views

What is known about $CFL \cap coCFL$?

CFL is the class of context-free languages; co-CFL the languages whose complements are context-free. So CFL $\neq$ co-CFL. Are there any nice characterizations or other basic facts about CFL $\cap$ ...
-2
votes
1answer
259 views

Intersection between context-free and context-sensitive language decidability [closed]

I'm trying to find a formal proof of the following fact: Given a context-free language, say $L_1$, and a context-sensitive language, say $L_2$, it is NOT decidable if their intersection is empty ...
4
votes
3answers
2k views

Ambiguity in regular and context-free languages

I understand the following claims to be true: Two distinct derivations of a string in a given CFG may sometimes attribute the same parse tree to the string. When there are derivations of some string ...
5
votes
1answer
117 views

Investigation of Symbol Minimal Context-Free Grammars for the Language $a^n$

Question Given the language $L_n = \{ a^n \}$ for a natural number $n \geq 2$. Is there a symbol minimal context-free grammar $G$ that generates $L_n$ and contains a rule of the form $A \rightarrow ...
0
votes
1answer
383 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 ...
12
votes
0answers
242 views

Are there variants of visibly pushdown automata that allow pushing of words onto the stack?

I'm wondering, are there any papers or research dealing with visibly pushdown automata, but allowing words, rather than single letters, to be pushed onto the stack. Alternately, a construction which ...
4
votes
1answer
360 views

Minimal context-free grammar for a regular language

Are there any algorithms for solving exactly the following question? Given a regular language L, represented as a finite automaton say, what is a CFG with minimal number of nonterminals that generates ...
3
votes
0answers
298 views

Variant of a proof using Ogden's lemma

I am trying to understand better the proof that the language $K=\{a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} is not context-free. (see It only looks like a homework problem…), and the use of ...
6
votes
0answers
207 views

Deciding if a language induced by a Presburger formula is context-free

Is the following problem decidable? Given $n$ and a Presburger arithmetic formula $\phi(x_1,x_2,\dots,x_n)$, determine whether the language $\{a_1^{i_1} \dots a_n^{i_n}:\phi(i_1,i_2,\dots,i_n)\}$ ...
-2
votes
1answer
162 views

Is the gist of English (or any equally familiar natural language) context-free? [closed]

When I say 'equally familiar natural language', I hope to ignore languages such as Arabic and Hebrew, of which I know absolutely nothing save an alphabet in the latter case. I am doing research in ...
11
votes
2answers
605 views

Does there exist an extension of regular expressions that captures the context free languages?

In many papers involving context-free grammars (CFGs), the examples of such grammars presented there often admit easy characterizations of the language they generate. For example: $S \to a a S b$ ...
3
votes
2answers
399 views

Context-free Grammar for a Context-free Language Intersecting a Regular Language (get the Maximum Number of Rules)

It is well known that the intersection of $L \cap R$ of a context-free Language $L$ and a regular Language $R$ is context-free. Each proof I have seen constructs a automaton (a PDA) that accepts $L$ ...
1
vote
0answers
193 views

Non-uniform CFG ambiguity decidability

The uniform version (the version which we normally see) of deciding whether a CFG (Context Free Grammar) is ambiguous is undecidable. But here I'd like to know something about the non-uniform version ...
1
vote
0answers
176 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 ...
5
votes
0answers
1k views

Eliminate ambiguity from CFG

CFG here stands for context-free grammar. I understand that: Deciding whether a CFG $G$ is ambiguous is undecidable. Deciding whether a CFL $L$ is inherently ambiguous is undecidable. My question ...
8
votes
1answer
178 views

Rational Functions and CFL

In my work arose the problem of classification CFL under rational functions images. In other terms, what class of languages form languages $T(L)$ , for fixed context free language $L$ and ...
6
votes
0answers
207 views

Language of stack configurations of a pushdown automaton

Consider a pushdown automaton $A$ with stack alphabet $\Gamma$. Let $L$ be the language on $\Gamma$ of the stack configurations encountered during accepting runs of $A$. Is $L$ a context-free ...
-5
votes
2answers
680 views

Deterministic CFL closure Property Homomorphism [closed]

I tried to research the following question with no results: Can you find one example where the following holds true: Let L = {xxxxxxx} be a deterministic-context-free Language and Let h(...) = xxxxx ...
5
votes
1answer
256 views

Minimal Number of Symbols in Context-Free Grammar for a Special One-Letter Language

Given is the language $$L_n = \{a^n\},$$ where $n$ is a natural number and $a$ is a letter. What are the productions/rules of a minimal context-free grammar according to the number of symbols of the ...
14
votes
1answer
968 views

Sufficient conditions for the regularity of a context-free language

It would be nice to collect a list of conditions that imply that a context-free language L is regular, i.e. conditions of the form: "if a given CFG/PDA has property P, then its languages is regular" ...
3
votes
0answers
327 views

Minimal context-free Grammar for a special one-letter Language

For natural numbers $n \geq 5$, $m \geq 2^{n-2} + 1$ the following context-free language is given: $$ L_{n,m} = \{ a^i | 2 \leq i \leq m \} \setminus \{a^{2^i}|2 \leq i \leq n-2\} $$ Find and ...
7
votes
0answers
934 views

Is there an ambiguity test for CFGs faster than trying all strings?

It is well known that testing whether a grammar is ambiguous is undecidable. It is however trivially decidable for any $G$ whether $L_n(G) := \{ w | w \in L(G) \wedge |w| \leq n \}$ for any $n \in ...
0
votes
1answer
196 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 ...
-1
votes
1answer
83 views

Issue in understanding conditional likelihood for a producton rule

The Equation1 in paper in link explains how to assign probability to a production rule. Fig1 explains with an example. Now, I have a problem in understanding how to work with this formula since it ...
20
votes
1answer
2k views

Can all unambiguous grammars be parsed in linear time?

When tinkering with noncanonical LR parsing, I thought up a parsing method (with infinitely sized tables, which makes it somewhat unpractical) capable of parsing exactly the unambiguous grammars in ...
-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 ...
8
votes
1answer
897 views

Non-CFL closure properties

I was asked the following by a student, and couldn't come up with a complete answer: Are there any closure properties for the class of languages that are not context free? It's fairly easy to find ...
27
votes
0answers
456 views

Eilenberg's rational hierarchy of nonrational automata & languages — where is it now?

In the preface to his very influential books Automata, Languages and Machines (Volumes A, B), Samuel Eilenberg tantalizingly promised Volumes C and D dealing with "a hierarchy (called the rational ...
11
votes
2answers
220 views

On $n$ dimensional manifolds and lattices

EDIT (By Tara B): I'd still be interested in a reference to a proof of this, as I had to prove it myself for my own paper. I'm looking for the proof of Theorem 4 that appears in this paper: An ...
14
votes
2answers
897 views

Permutation phrases with LR parsing

A permutation phrase is an extension to the standard (E)BNF context free grammar definitions: a permutation phrase $\{ A_1, \dots, A_n \}$ contains $n$ productions (or equivalently, nonterminals) ...
7
votes
1answer
5k views

Why is non-determinism (Push-down automata) necessary?

I would like to know why for the recognition of context-free languages only non-deterministic push-down automata (DPA=NPDA) work. Why do deterministic push-down automata (DPDA) not recognize such ...
5
votes
1answer
309 views

Can Bencodes Be Described With a Context-Free Grammar?

Bencoding is the encoding scheme used by Bittorrent applications. You’re probably most familiar with bencoding via the .torrent file format used by Bittorrent ...
20
votes
10answers
1k views

For a language to be programmable, is it mandatory that it be based on a context free grammar

Practically, for a language that can eventually be compiled/transformed into system level instructions, is it necessary that it be a context free grammar? ex: Are all programming/scripting languages ...