Linked Questions
124 questions linked to/from How to prove that a language is context-free?
6
votes
2
answers
10k
views
Converting to CFG from a CFL? [duplicate]
I am trying to learn CFG. Now to make a CFG from a CFL it is really difficult for me.
Is there any simple rule or steps so that I can easily find a CFG for a CFL. I am trying to solve one problem ...
- 173
0
votes
1
answer
8k
views
prove language is Context-free and not regular [duplicate]
I have to prove that $\left \{ a, b \right \}^{\ast} - \left \{ a^ib^i | i\geq 0 \right \}$ is a context-free language and it's not regular.
So far I've got that this language is not regular because ...
- 255
1
vote
2
answers
2k
views
Tips for creating “Context Free Grammar” [duplicate]
I am new to CFG's, Can someone give me tips in creating CFG that generates some language
For example
$L =\{ w v w^R \mid v,w\in \{a,b\}^*\wedge|v| \text{ is even } \}$, where $w^R$ is the reverse ...
3
votes
2
answers
3k
views
how to prove that every finite language is context-free? [duplicate]
I am trying to prove that every finite language is context-free, is there any type of way that I could do it effectively?
- 63
0
votes
1
answer
3k
views
Create CFG and pushdown automaton for {ww} [duplicate]
I've been trying to make a CFG, a pushdown automaton and a regular expression for the language
$\qquad L(M) = \{ww : w \in \{a, b\}^*, |w| \text{ is even}\}$.
I understand how the reverse of the ...
- 125
-2
votes
1
answer
3k
views
How to write CFG for languages [duplicate]
How do you write the CFG for the following language:
{ax by c ax+y}
Is there some formula or rules I need to follow? An explanation will be so appreciated.
What I tried is:
First I broke ax+y into ...
- 101
0
votes
3
answers
2k
views
Is it possible to prove Language L context-free? [duplicate]
Give a question:
Language L= {a^n b^(n+m) a^m}, where both n and m are >=0. Is L context-free or not.
If the answer is yes, can I use the following PDA to prove it?
Since {a^n b^(n+m) a^m}={a^n b^n ...
-1
votes
1
answer
1k
views
How to find the Context-free grammars for this language [duplicate]
give a context-free grammar describing the language L={w∈{a,b}∗∣w is of the form xby, where |x|>|y|}.
I had one solution like this
...
- 99
-1
votes
1
answer
996
views
Construct grammar given the following language [duplicate]
Construct grammar given the following language!
$ L = \{(ab)^{n+1}u(ba)^n|n>0, l_c(u) = 1, u\in\{a,c,d\}^* \}$
My interpretation in a less accurate way:
$(ab)^{n+1}$ says we need to concatenate $...
- 23
0
votes
1
answer
488
views
Context free grammar for this language [duplicate]
Is this language Context Free?
$L=\{a^{n+3} b^{2m} \mid n \neq m \}$
I think that I could split the languages into $L_1$ and $L_2$ with the conditions $n<m$ and $n>m$, provide 2 CF grammars ...
- 3
0
votes
1
answer
202
views
Build a context-free grammar for a context-free language [duplicate]
A context-free language is defined by its description:
$L=(a^{2k} \space b^n \space c^{2n} \mid k \geq 0, \space n > 0)$
For example:
$bcc, aabcc, aabbcccc, bbcccc$
How to build a context-free ...
- 135
1
vote
1
answer
256
views
Make a Pushdown automata that accepts a language defined by strings that contain the same number of a and b [duplicate]
How do I build a pushdown automata that accepts the language over the alphabet $\Sigma = \{a, b\}$, defined by the strings $w$, such that $|w|_a = |w|_b$?
I'm sorry I can't give any approach of what ...
- 11
0
votes
1
answer
235
views
What context free grammar generates the language $L(G) = \{a^ib^jc^{2i}d^m\}$ [duplicate]
I am struggling to think of the context-free grammar that generates the language $L(G) = \{a^ib^jc^{2i}d^m\}$, where $i$, $j$ and $m$ are natural numbers.
Also, in general, are there any good methods ...
- 107
1
vote
0
answers
249
views
Is $\{a^mb^nc^{mn}\mid m>n\}$ a context-free language? [duplicate]
Been trying to figure it out for an hour myself and another hour looking around, I cannot find anything with the $c^{mn}$ part.
$$L=\{a^mb^nc^{mn}\mid m>n\}$$
- 11
3
votes
1
answer
188
views
Creating a CFG that connects lengths of three blocks [duplicate]
I have to create a CFG which generates
$$\{a^n (ab)^n c^m d^\ell e^k \mid n>0, k, \ell, m\ge0, k<m, m=\ell+k\}$$
The first part is easy enough, I came up with
$$\begin{align*}
S &\to ...
