Linked Questions

7
votes
2answers
5k 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 ...
0
votes
1answer
5k 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 ...
2
votes
2answers
1k 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 ...
-2
votes
1answer
2k 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 ...
-1
votes
1answer
2k 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 ...
3
votes
2answers
2k 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?
-1
votes
1answer
909 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 $...
0
votes
3answers
786 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
1answer
410 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 ...
0
votes
1answer
388 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 ...
0
votes
1answer
162 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 ...
0
votes
1answer
150 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 ...
-2
votes
1answer
63 views

Pushdown automaton for language with “or” [duplicate]

Find a pushdown automaton accepting the language $$L=\{A^i B^j C^k \mid 2k \le i \le 3k \text{ or } j \neq i+k \}.$$ I can't construct the automaton because I can only imagine it with multiple stacks ...
3
votes
1answer
90 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 ...
1
vote
0answers
98 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\}$$

15 30 50 per page