The context-free-languages tag has no wiki summary.
-4
votes
0answers
23 views
Grammars for matching properties of a left and right half of a string
I know that w#w is not a context-free language, but what about {xy | where |x| = |y|, x contains the same number of as as y [and therefore the same number of bs]}.
-6
votes
0answers
59 views
Context free language [closed]
Hi everyone i wonder DCFL(Deterministic Context free language ) - Regular language should be context free or not ? Is there anyone who can help me about this ? thanks in advance
-4
votes
0answers
35 views
language of all the palindrome strings of a CFL is CFL [closed]
How do you prove that the language of all the palindrome strings of a context free language is itself a context free language? In other words prove that $L'$ is context free if $L$ is context free, ...
-2
votes
1answer
135 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 ...
10
votes
2answers
271 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
1answer
133 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$ ...
8
votes
1answer
158 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 ...
3
votes
0answers
136 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
206 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
152 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 ...
3
votes
0answers
254 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 ...
-1
votes
1answer
79 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 ...
8
votes
1answer
413 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 ...
19
votes
0answers
189 views
Eilenberg's rational hiererchy 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 ...
10
votes
2answers
191 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 ...
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 ...
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: ...
