Context-free grammars give a set of rules for generating formal languages. The formal languages generated by a context-free grammar are known as context-free languages.

learn more… | top users | synonyms (1)

3
votes
1answer
25 views

Need to create a context-free language

I need to create a context-free language for the following language. $$L = \{w\in\Sigma^\ast \mid w = a^k b^m c^n \text{ where } k,m,n\in\mathbb N \text{ and } k<m \vee k>n\}$$ Here ^ is the ...
0
votes
1answer
26 views

Context-free language or not

It is language: $L = \left\lbrace a^ib^jc^kd^l \mid i+k < j+l+3 \right\rbrace$ Is it context-free or not? I have two versions: 1)Pumping lemma(refute): get a word $uvxyz = aabcd$ if $i=2$ we get ...
0
votes
2answers
656 views

Find a CFG for L = { a^nb^m : n != m }

This question is upcoming for my midterm and I can't figure it out. My professor broke it down in two statements (n>m) and(m>n) and left us at that. Find a context free grammar for $L = \{ a^n b^m : ...
0
votes
1answer
38 views

Context free grammar $\{a^n b^m c^k\; : \;k>m \; \; k>n\}$

Is this a CFL? $$\{a^n b^m c^k\; : \;k>m \; \; k>n\}$$ When on seeing $a$'s and $b$'s I push them onto stack and as I see $ c$ as input if $ TOS$ is $b$ ,I pop them ,again if $TOS$ is a,I pop ...
1
vote
0answers
16 views

If $L$ is context-free, then $L$ is regular

Let $L \subset \{a\}^*$ and assume that $L$ is context-free. Prove that $L$ is regular. Please hint me.
2
votes
2answers
311 views

Example of a non context-free language whose complement isn't context-free as well

The language $L=\{a^{2^n} \mid n \geq 0\}$ isn't context free (easily proved using the pumping lemma). But what about its complement? It seems to me that it's unlikely for it to be context free, but ...
0
votes
1answer
21 views

show that $L = \{a^n b^m | m\neq n\}$ is context free language

show that $L = \{a^n b^m | m\neq n\}$ is context free language using closure under union My attempt is show L1 = a^n b^m n>m is context free and show L2 = a^n b^m n less than m is also context ...
4
votes
3answers
925 views

What is the CFG of the language that generates all strings over alphabet $\{a, b, c\}$?

The most obvious one that I found was, $$S \rightarrow SSS | A | B | C$$ $$A \rightarrow Aa | \epsilon$$ $$B \rightarrow Bb | \epsilon$$ $$C \rightarrow Cc | \epsilon$$ However, I realize this CFG is ...
0
votes
0answers
11 views

4th case in Ogden's Lemma

I'm trying to understand Ogden's Lemma and I know there are four cases, but in the next example I can only find 3: A = {$0^n1^m0^k$ | k = max{n,m}} is not context free: Assuming: z = $0^k1^k0^k ∈ A$ ...
0
votes
1answer
22 views

Showing that calculus are (not) equivalent

Let $\mathcal{A} = \{ x,y \}$ be an alphabet. Consider the following rules for derivation: $R_1 : \begin{array}{c} \hline \epsilon \end{array},\\R_2: \begin{array}{c} z \\\hline zx \end{array},~ R_3: ...
1
vote
1answer
363 views

Eliminating Epsilon Production for Left Recursion Elimination

Im following the algorithm for left recursion elimination from a grammar.It says remove the epsilon production if there is any I have the following grammer ...
0
votes
0answers
17 views

give context-free grammar for language $L=\{w\in P:\#_a(w)-\#_b(w)\equiv 2 (\mod 3)\}$

let $P$ will be set of palindroms $P\subseteq (a+b)^*$ $L=\{w\in P:\#_a(w)-\#_b(w)\equiv 2 (\mod 3)\}$ $\#_a(w)=$ number of letters $a$ in word $w$. So, my idea: possible pair of rests, are: ...
0
votes
0answers
19 views

Check if language is context free

The language is the set of finite prefixes of the infinite word: $a^1b^2a^3b^4 \dotsm$ The question is to show that this language is not context-free. So to my eye, it is not context free, let $p$ ...
1
vote
1answer
13 views

Check if $L$ is regular then $L'$ is regular (and and vice versa)

let's define $w\leftrightarrow v$. It does mean that we may "create" $w$ using word $v$ in following way: every single letter $x\in \Sigma$ in word $v$ may be replaced by $xx$, and every double ...
0
votes
0answers
7 views

If is true that: if $L$ is context free then $Cycle(L)$ is context free?

$L$ is context free. $Cycle(L)$ is context free. $Cycle(L)=\{uv|vu\in L\}$ Is is true that $Cycle(L)$ is also context free ? I know that I ought to show my attemptions, but really - I can't start in ...
0
votes
1answer
10 views

Check if languages $K$ and $L$ are non-context free

$K = \{a^kba^lba^n|kk+l=n\} $ $L=\{a^kba^lba^n|kl=n\} $ Firstly, let's consider language $K$. I use pumping lemma to show that $K\notin CFG$. Let $s=a^pba^pba^{2p}=uvxyz$ Thanks to pumping lemma: ...
0
votes
0answers
7 views

$L$ is context free, and $R$ is regualar. Show that $R^{-1}L$ is context free

$R^{-1}L=\{s:\exists t_{\in R}\ ts \in L\}$ Firstly, I want to show my idea, I ask for checking it. 1. Let $M$ will be PDA for $L$ and $N$ for $R^{-1}$. 2. Use $\epsilon$-transitions to guessing ...
0
votes
1answer
30 views

What is turing machine for $a^i b^j c^k$ where $i=j$ or $j=k$

I am trying to construct turing machine for $a^ib^jc^k$ where $i=j$ or $j=k$. Every time I come up with solution its getting fail for some other string.
1
vote
1answer
25 views

What does this CFG accept?

I am not sure what this language accepts: $S \to 01S2A\,|\,\epsilon$ $A \to 1A\,|\,1$ I thought something like: $(01)^i(21)^i1^n$ But then I didn't know how to handle all the 1's that can come ...
0
votes
1answer
50 views

Context-free languages closure property

Trying to rove that the set of all context-free languages over a language Ξ£ is closed under TRIPLE where TRIPLE (L1, L2, L3) = L1L2L3. Pretty much, TRIPLE, applied to three languages yield the ...
0
votes
1answer
18 views

Syntaxes one can describe using BNF?

How can one tell if certain syntax is describable by BNF? Is it anything i can describe with a context free grammar? So are programming languages like C,java.. describable by BNF? or does it depend ...
1
vote
0answers
14 views

Check if $L\in CFG$ then $L'\in CFG$

Check if $L\in CFG$ then $L'\in CFG$ $L'=\{w|ww^R\in L\}$ So, I show counterexample. Let $L=\{a^ib^ja^ib^l|i,j,l \ge 0\}\cdot \{b^za^xb^za^y|x,y,z\ge 0\} = \{a^ib^ja^ib^lb^za^xb^za^y|x,i,j,l,y,z\ge ...
1
vote
0answers
20 views

prove that language is non-context free

Prove that $A=\{wtw^R|w,t\in \{0,1\}^*\wedge |w|=|t|\}\notin CFG$ I use pumping lemma: Let $p$ will be length of pumping.Given $s=1^p0^p1^p=uvxyz $ We know, that (because of the fact that $|vxy|\le ...
0
votes
2answers
47 views

Prove that language is context-free $C=\{x\#y \mid x,y\in \{a,b\}^*\wedge x\neq y\}$

Prove that this language is context-free: $C=\{x\#y|x,y\in \{a,b\}^*\wedge x\neq y\}$. I try to construct a grammar: $S\rightarrow C_a\#C_b|C_b\#C_a$ $C_a\rightarrow XC_aX|a$ $C_b\rightarrow XC_bX|b$ ...
2
votes
1answer
40 views

Is this language context-free or not?

I have a problem to solve, the problem is: Is the language of strings $$L=\{0^x1^y:x\nmid y\}$$ context free? I suspect it isn't, I spent some time trying to make a grammar that could ...
0
votes
2answers
40 views

Dollar Sign in Context Free Language

I have a homework about find the pumping lemma in Context Free Language. The last one I couldn't solve: $L = \{a^i \$ a^{3i} \$ a^{5i} \mid i \in \mathbb{N} \}$ What does the dollar symbol mean ...
1
vote
1answer
41 views

Write grammar for given language

I'm trying to write a grammar for the language below: $$(a+b)^*βˆ’\{𝑀𝑀𝑀 ∢ 𝑀\in\{a,b\}^*\}$$ could anyone help me?
1
vote
1answer
332 views

Context free grammar to pushdown automata…

<expr> βˆ’β†’ <term> | <expr> + <term> <term> βˆ’β†’ <factor> | <term> Γ— <factor> <factor> βˆ’β†’ (<expr>) | b ...
1
vote
1answer
22 views

Prove that $Y=\{w|w=t_1\#t_2\#…\#t_k\}$ is not context free

$Y=\{w|w=t_1\#t_2\#...\#t_k |t_i \in 1^*\wedge \forall_{i\neq j}t_i\neq t_j\wedge k\ge 0 \}$ Prove that $Y$ is not context free. So, let's $p$ will be pumping lemma length. ...
1
vote
1answer
21 views

Repeated rules in Chomsky normal form

My question is simple, when you're converting a grammar to CNF, what happens when a rule begins to repeat multiple times? ΒΏIt's good to end with rules like $U_1 \rightarrow SB, U_2 \rightarrow SB, ...
0
votes
3answers
30 views

prove that language is not free context

$F=\{\,a^ib^j\mid i=kj\text{ for some $k>0$}\,\}$ Prove that this language is not context free. The only thing that comes to my mind is pumping lemma; Let $p$ be the pumping length. Given ...
1
vote
0answers
46 views

Construct Context Free Grammar for $\{0,1\}^*-\{www~|~w\in\{0,1\}^*\}$

I'm working on the exercises in "Problem Solving in Automata, Languages, and Complexity" and I've run into the below problem. The question asks to construct a CFG for the language , and I just can't ...
0
votes
1answer
57 views

Creating a language

I am given a list languages, say $L$, over alphabet $\{a,b\}$. A function $f$ is defined such that $f(i) = L$ for $i ∈ N$. I am trying to a construct a language $D$ which is not in the list (aka. $D ...
0
votes
1answer
39 views

context-free languages operation closure

The following operation is defined on formal languages. $ operation1(L) = \lbrace w \ | \ wxy \in L, \ \forall x \forall y \ (|x|=|w|) \ \wedge (|y| = |w| ) \rbrace $ Prove that context-free ...
0
votes
2answers
19 views

prove that set of palindroms such that $\#_0(w)=\#_1(w)$ is not CFG

$B$ - set of palindroms such that number of $1s$ is equal to number of $0s$. Every palindrom $\in \{0,1\}^*$ And my task let me that $B$ is not CFG. But I don't agree with it. Because of the fact that ...
1
vote
1answer
27 views

Is $L = \{0^{i}1^{i}0^{j}1^{i} | i, j > 0\}$ a context free language?

Is the following argument correct? $L = (A \circ B) \cap C$ where, $A = \{0^{i}1^{i}$ $|$ $i > 0\}$ $B = \{0^{j}1^{i}$ $|$ $i, j > 0\}$ $C = \{0^{i}1^{j}0^{k}1^{i}$ $|$ $i, j, k > 0\}$ We ...
2
votes
1answer
29 views

Show that language is context free

Show that language is context free $E=\{a^ib^j|i\neq j\wedge 2i\neq j\}$ Look at my solution please: I use the fact that languages context free are closer under sum $E=E_1\cup E_2\cup E_3 = ...
1
vote
1answer
35 views

Proving with pumping lemma

I am trying to prove that the follow language is not regular L = {w ∈ {0, 1}βˆ— | the number of 1s in w is one more than the number of 0s} My approach was to prove that it is regular and prove by ...
2
votes
0answers
58 views

How to show $L = \{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$ is ambiguous?

I'm recently familiar with this site and prefer to ask a very hard problem :) How can we prove that the following language is inherently ambiguous? $$L = \{a^n b^m c^p: n\neq m\} \cup \{a^n b^m ...
0
votes
1answer
14 views

Find CFG for language $\#_a(w) = 2\#_b(w)$

$L=\{w\in (a+b)^*:\#_a(w) = 2\#_b(w)\}$ I can think grammar: $S\rightarrow abSa\ |\ aaSb\ |\ baSa\ |\ bSaa\ |\ aSba\ |\ aSab\ |\ SS$ But I couldn't prove that it is full (generates all words). When it ...
1
vote
1answer
45 views

Is it possible to write an Unambiguous Grammar for Two Hard Language ?!?

I came across a very hard interview exam. It was asked wrote an unambiguous grammar for two following language, Who can hint it to solve it? 1) $L = \{a^n b^{2n} c: n\geq 0\} \cup \{a^{2n} b^n d: ...
1
vote
1answer
52 views

Sentences, Formal Grammars with derivation (parse) trees

I've been reading / studying formal grammars for the past few weeks and I came across a question that puzzled me and I cannot seem to get my head around it for some reason. ...
1
vote
1answer
31 views

Context-free grammar

Although the empty word $\epsilon$ is allowed in context-free grammars, it is always possible to describe any context-free language using a grammar in which the only nullable symbol is the start ...
2
votes
2answers
47 views

Finding a grammar for given language

So for this problem we are given a language and we have to find the grammar for that set. I am confused and what the constructors should be. The language in this problem is: $\{bb, bab, baab, ...
1
vote
1answer
51 views

Finite groups acting on strings.

Let $s = abcdandsoon.. \ \in \Sigma^*$. Let $|s| = n$ be the length of $s$. Consider all permutations of the positioned symbols that make up $s$, such that $s$ is fixed under the permutation. So if ...
0
votes
2answers
93 views

Context free grammar for AN

I need to write Context free grammar for describing moves in a game of chess using the Algebric Notation. Can anyone help me get started. f.ex. how do I write this for this move: Bb5 Bd7.
0
votes
1answer
104 views

Proving some property of a Formal Logic Language [duplicate]

I am stuck at this problem: Let $\Sigma = \{\lnot,\lor,\land,\rightarrow,\leftrightarrow,(,),P_1,...,P_n\}$ be an alphabet. Now let's define the set of logical expressions $\mathscr{L} \subseteq ...
1
vote
2answers
131 views

Proving a property of a Logic Formal Language

I am stuck at this problem: Let $\Sigma = \{\lnot,\lor,\land,\rightarrow,\leftrightarrow,(,),P_1,...,P_n\}$ be an alphabet. Now let's define the set of logical expressions $\mathscr{L} \subseteq ...
1
vote
0answers
42 views

Context free grammars for generating mathematical expressions

I am looking for some resources on CFGs capable of generating mathematical expressions. For example an expression like the one below $expression = a + 2b + 4ac$ Where a,b,c are some terminal ...