Linked Questions

6 votes
2 answers
8k 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 ...
user avatar
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 ...
user avatar
  • 245
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 ...
user avatar
-2 votes
1 answer
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 ...
user avatar
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?
user avatar
  • 63
0 votes
1 answer
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 ...
user avatar
  • 125
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 ...
user avatar
-1 votes
1 answer
983 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 ...
user avatar
  • 99
-1 votes
1 answer
984 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 $...
user avatar
  • 23
0 votes
1 answer
471 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 ...
user avatar
  • 3
0 votes
1 answer
186 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 ...
user avatar
0 votes
1 answer
182 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 ...
user avatar
1 vote
0 answers
196 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\}$$
user avatar
1 vote
1 answer
130 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 ...
user avatar
  • 11
0 votes
0 answers
153 views

Is this language context-free? $\Sigma$ = {a,b,#} L = {x1#x2#...#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} [duplicate]

Is this language context-free? $\Sigma$ = {a,b,#}, L = {x1#x2#...#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} I think it is not, because the PDA can't memorize ...
user avatar
  • 21

15 30 50 per page
1
2 3 4 5
8