Questions tagged [context-free]
Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.
1,681
questions
8
votes
1
answer
580
views
Is this language Context-Free?
Is the language
$$L = \{a,b\}^* \setminus \{(a^nb^n)^n\mid n \geq1 \}$$
context-free? I believe that the answer is that it is not a CFL, but I can't prove it by Ogden's lemma or Pumping lemma.
2
votes
1
answer
1k
views
Eliminating useless productions resulting from PDA to CFG converison
In my class we used a Pushdown Automata to Context Free Grammar conversion algorithm that produces a lot extraneous states.
For example, for two transitions, I am getting the following productions
...
- 461
32
votes
4
answers
31k
views
How to prove that a grammar is unambiguous?
My problem is how can I prove that a grammar is unambiguous?
I have the following grammar:
$$S
→ statement
∣ \mbox{if } expression \mbox{ then } S
∣ \mbox{if } expression \mbox{ then } S \mbox{ else } ...
- 521
3
votes
2
answers
8k
views
Context-free grammar for $\{ a^n b^m a^{n+m} \}$
I've got a problem with this task. I should declare a context-free grammar for this language:
$\qquad \displaystyle L := \{\, a^nb^ma^{n+m} : n,m \in \mathbb{N}\,\}$
My idea is: We need a start ...
- 521
4
votes
1
answer
9k
views
Removing Left Recursion from Context-Free Grammars - Ordering of nonterminals
I have recently implemented the Paull's algorithm for removing left-recursion from context-free grammars:
Assign an ordering $A_1, \dots, A_n$ to the nonterminals of the grammar.
for $i := 1$ to $n$ ...
clebert
9
votes
1
answer
1k
views
Proof that $\{⟨M⟩ ∣ L(M) \mbox{ is context-free} \}$ is not (co-)recursively enumerable
I would like to use your help with the following problem:
$L=\{⟨M⟩ ∣ L(M) \mbox{ is context-free} \}$. Show that $L \notin RE \cup CoRE$.
I know that to prove $L\notin RE$, it is enough to find a ...
- 462
24
votes
1
answer
4k
views
Decide whether a context-free languages can be accepted by a deterministic pushdown automaton
Given a context-free grammar G, there exists a Nondeterministic Pushdown Automaton N that accepts exactly the language G accepts. (and visa versa)
There may also exist a Deterministic Pushdown ...
- 709
10
votes
1
answer
12k
views
Relation between simple and regular grammars
I am reading "An Introduction to Formal Languages and Automata" written by Peter Linz and after reading the first five chapters I face below problem with
simple and regular (especially right linear) ...
- 203
1
vote
3
answers
394
views
Use closure properties to transform languages to $L := \{ a^nb^n : n\in \mathbb N \}$
For the purpose of proving that they are not regular, what closure properties can I use to transform the languages
$L_a = \{ a^*cw \mid w \in \{a,b \}^* \land |w|_a = |w|_b \}$ and
$L_b = \{ab^{i_1}...
- 879
10
votes
3
answers
3k
views
If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?
I'm am stuck solving the next exercise:
Argue that if $L$ is context-free and $R$ is regular, then $L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} $ (i.e. the right quotient) is context-...
- 201
4
votes
1
answer
675
views
A context free grammar proof
There is a problem which I cannot solve. If you give a tip I will be very glad.
Prove that following language is not context free:
$L= \{ a^nb^m | \gcd(n,m) = 1 \}$.
It can be proven using the ...
- 41
5
votes
1
answer
387
views
The operator $A(L)= \{w \mid ww \in L\}$
Consider the operator $A(L)= \{w \mid ww \in L\}$. Apparently, the class of context free languages is not closed against $A$. Still, after a lot of thinking, I can't find any CFL for which $A(L)$ ...
- 1,697
7
votes
4
answers
542
views
Why does $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ generate a context free language for regular $L$?
How can I prove that the language that the operator $A$ defines for regular language $L$ is a context free language.
$A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$, where $x^R$ is the ...
- 1,697
5
votes
2
answers
459
views
Is $A=\{ w \in \{a,b,c\}^* \mid \#_a(w)+ 2\#_b(w) = 3\#_c(w)\}$ a CFG?
I wonder whether the following language is a context free language:
$$A = \{w \in \{a,b,c\}^* \mid \#_a(w) + 2\#_b(w) = 3\#c(w)\}$$
where $\#_x(w)$ is the number of occurrences of $x$ in $w$.
I can't ...
- 1,697
5
votes
1
answer
409
views
Closure against the operator $A(L)=\{ww^Rw \mid w \in L \wedge |w| \lt 2007\}$
I would like your help with the following question:
Let $L$ be a language, and operator $A(L)=\{\,ww^Rw \mid w \in L\ \wedge\ |w| \lt 2007\,\}$ where $x^R$ is the reversed string of $x$. Which of ...
- 1,697
5
votes
1
answer
2k
views
Chomsky normal form and regular languages
I'd love your help with the following question:
Let $G$ be context free grammar in the Chomksy normal form with $k$
variables.
Is the language $B = \{ w \in L(G) : |w| >2^k \}$ regular ?
...
- 1,697
4
votes
4
answers
8k
views
Prime number CFG and Pumping Lemma
So I have a problem that I'm looking over for an exam that is coming up in my Theory of Computation class. I've had a lot of problems with the pumping lemma, so I was wondering if I might be able to ...
- 1,115
15
votes
2
answers
1k
views
Are the Before and After sets for context-free grammars always context-free?
Let $G$ be a context-free grammar. A string of terminals and nonterminals of $G$ is said to be a sentential form of $G$ if you can obtain it by applying productions of $G$ zero or more times to the ...
- 9,036
4
votes
3
answers
200
views
Language of the graph of an affine function
Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let : be a symbol distinct from any digit. Let $a$ and $b$ ...
10
votes
5
answers
1k
views
Language of the values of an affine function
Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let $a$ and $b$ be integers, with $a > 0$. Consider the language of the decimal expansions ...
16
votes
2
answers
2k
views
Decidablity of Languages of Grammars and Automata
Note this is a question related to study in a CS course at a university, it is NOT homework and can be found here under Fall 2011 exam2.
Here are the two questions I'm looking at from a past exam. ...
- 1,115
11
votes
2
answers
6k
views
How can I prove this language is not context-free?
I have the following language
$\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\}$
I am trying to determine which Chomsky language class it fits into. I can see how it could be made using a context-...
- 435
10
votes
1
answer
476
views
Given a string and a CFG, what characters can follow the string (in the sentential forms of the CFG)?
Let $\Sigma$ be the set of terminal and $N$ the set of non-terminal symbols of some context-free grammar $G$.
Say I have a string $a \in (\Sigma \cup N)^+$ such that $x a y \in \mathcal{S}(G)$ where $...
- 203
14
votes
2
answers
13k
views
Are all context-free and regular languages efficiently decidable?
I came across this figure which shows that context-free and regular languages are (proper) subsets of efficient problems (supposedly $\mathrm{P}$). I perfectly understand that efficient problems are a ...
- 2,193
53
votes
1
answer
24k
views
Show that { xy ∣ |x| = |y|, x ≠ y } is context-free
I remember coming across the following question about a language that supposedly is context-free, but I was unable to find a proof of the fact. Have I perhaps misremembered the question?
Anyway, here'...
- 20.2k
98
votes
5
answers
103k
views
How to prove that a language is not context-free?
We learned about the class of context-free languages $\mathrm{CFL}$. It is characterised by both context-free grammars and pushdown automata so it is easy to show that a given language is context-free....
- 72k
12
votes
1
answer
5k
views
Is an infinite union of context-free languages always context-free?
Let $L_1$, $L_2$, $L_3$, $\dots$ be an infinite sequence of context-free languages, each of
which is defined over a common alphabet $Σ$. Let $L$ be the infinite union of $L_1$, $L_2$, $L_3$, $\dots $;
i....
- 2,193
7
votes
1
answer
690
views
How to convert a non-embedding context free grammar to regular grammar?
A context-free grammar is said to be self-embedding if and only
if contains a derivation of the form $\xi\stackrel*\Rightarrow u\xi v$, where $\xi$ is a non-terminal and $u$, $v$ are some non-empty ...
dalibocai
6
votes
3
answers
3k
views
Closure of Deterministic context-free languages under prefix
For a formal language $L \subseteq \Sigma^{*}$ I define the set Pref(L) to be:
$\text{pref}(L) = \{\alpha \in \Sigma^{*} : \exists \beta \in \Sigma^{*} \text{ such that } \alpha \beta \in L\}$
ie. ...
- 1,141
13
votes
1
answer
7k
views
Is there a context free, non-regular language $L$, for which $L^*$ is regular?
I know that there are non-regular languages, so that $L^*$ is regular, but all examples I can find are context-sensitive but not context free.
In case there are none how do you prove it?
- 583
7
votes
1
answer
801
views
Converting a context free grammar to a PDA -- is my solution correct?
I'm reviewing for my midterm and wanted to post this to see if anyone can spot any errors. Im supposed to make a PDA that recognizes this CFG:
$\qquad\begin{align}
S &\to R1R1R1 \\
R &\to ...
jfisk