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)

0
votes
1answer
22 views

Proving $L=\{a^{n+3}b^{2m}|n≠m\}$ is not context free using the pumping lemma

Say if the language is context-free or not. If it is, write a context-free grammar, if not, demonstrate using the pumping lemma. $L=\{a^{n+3}b^{2m}|n≠m\}$ I have seen a lot of examples using the ...
1
vote
1answer
25 views

How to prove numerical formula about strings in context-free language?

Consider the the alphabet $\{0,1\}$ and the grammar $S\to 10,\, S\to 1SS0$. Define $P$ to be the set of all those strings and $P_n$ be the set of all strings in $P$ in which the substring $10$ occur ...
6
votes
1answer
86 views

Do all logics have formula syntax specified by context-free grammar?

I think propositional logic formulas syntax could be specified by context-free grammar with production rule below, where $A$ generates a finite string of $a_0, a_1$ stands for an atomic formula ...
1
vote
1answer
24 views

language generated by context free grammar G

I have a question to find the language generated by $G = (N, Σ, P, S)$ $N = ({S, A, B})$, $Σ = ({a, b})$, and $P = {S → aAa | bAb, A → aAa | bAb | B, B → aB | bB | ε}$ This generates strings of the ...
1
vote
1answer
47 views

Is this a free magma?

Given a context-free grammar $S\to(),S\to(SS)$, which generates all sentences of matching brackets in expressions of binary (possibly non associative) operations, and let $P$ be the set of all these ...
1
vote
1answer
439 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 ...
1
vote
1answer
58 views

What is the context-free grammar for $0^{n}1^{2n+1}0^{n}$

context free grammar for $0^{n}1^{2n+1}0^{n}$ I've tried several different methods to find it but I can't figure out how to make both sides opposite to each other...please help I've been working on ...
0
votes
1answer
32 views

Using the Pumping Lemma to show that $\{a^nb^{n^2} : n\in \mathbb{N} \}$ is not a context-free language

Consider the language $L= \left\{a^nb^{n^2} : n\in \mathbb{N}\right\}$. I want to prove that this language is not context-free by using the Pumping-Lemma for context-free languages. So, I picked the ...
0
votes
2answers
42 views

Context free grammar problems

Im having trouble doing the following context free grammer questions, the book im using doesnt cover this in the same way so im having trouble just understanding the questions, let alone doing them. ...
10
votes
2answers
2k views

An efficient way to determine if two context free grammars are equivalent?

I'm wondering if there's an efficient way of checking to see if two context free grammars are equivalent, besides working out "test cases" by hand (ie, just trying to see if both grammars can generate ...
1
vote
2answers
27 views

What are some quick things to look for to see if a language is regular or context-free

Without using proofs or pumping lemma, but just by looking at the given language by eye, what are some quick tips and techniques that can be used to see that a language is regular, or that a language ...
0
votes
1answer
71 views

Construct grammar $\ a^i b^j c^{i+j} b^j a^i $

I've been going through old exams at my college and I found this problem that I haven't yet been able to solve. Construct grammar defined on the alphabet $\ \{{a, b, c}\} $ which generates strings of ...
0
votes
1answer
16 views

Proving that a language with a regular expression is context-free

If L = {ww : w ∈ L(1*01*)} it means that w = $1^a$0$1^b$ and ww = $1^a$0$1^b$$1^a$0$1^b$ If I want to prove that this language is context-free by giving a context-free grammar, can I give a CF ...
3
votes
3answers
8k views

Question regarding Context Free Grammar exercises

I'm working on the exercises in "An Introduction to Formal Languages and Automata" 4th Ed textbook by Peter Linz. Since there are too few answers given in the back of the book, I wasn't able to check ...
0
votes
1answer
19 views

Prove that language is non-context free $L=\{a^{n^2}b^n|n\ge 0\}$

$\{a^{n^2}b^n|n\ge 0\}$ Is there any way to solve it beyond Pumping lemma ?
0
votes
1answer
43 views

Describe this language that is generated by Context Free Grammar

Describe this language that is generated by a Context Free Grammar $S \to SS$ $S \to XXX$ $X \to aX \mid Xa \mid b$
1
vote
1answer
15 views

Creating a CFL - based off unknown Regular language

Suppose $A\subseteq\Sigma^{\ast}$ is a regular language. Let $B=\{xy^R:x,y\in\Sigma^* , |x|=|y|, x \ XOR \ y \in A\}$ Prove that B is context free. I am struggling with understanding B. My only ...
2
votes
0answers
29 views

Stuck in a Context-Free Proof

I am trying to work through the pumping lemma for CFLs. $L_1 = \{0^n 1^{mn} : n,m \in \Bbb N\}$ I am trying to find a contradiction. I have currently chosen $z= 0^p1^{2p}$ to be my string. Then ...
0
votes
1answer
17 views

Using Union to prove a context-free language? [closed]

I am working through many examples and I seem to have confused myself and made all the questions rather trivial. If I have the CFLs, $L_1 = \{1^n 0^{mn} : n,m \in \Bbb N\}$ and $L_2 = \{1^m 0^n : ...
1
vote
0answers
11 views

is the suggested PDA correct?

so i have this language $$ L = \{x^{i} v^{j} z^{j+2} w^{k} v^{i+k} | i,j,k \ge 0 \}$$ i made this PDA for it . states $ = \{q_0 ... q_5 , final\} $ alphabet $= \{ x,v,z,w \}$ stack ...
1
vote
2answers
1k views

Confusion related to type 0 and type 1 grammar

I have this confusion related to type 1 grammar and type 0 grammar Lets say I have this type 1 grammar $$ S \rightarrow aSb, S \rightarrow ab $$ Now if I want to generate the null string and I add ...
1
vote
0answers
21 views

Context-Free Grammar production rules and terminals

For a context-free grammar G = (V,T,S,P) If one production rule of G is A -> nBC where n ∈ T*, does it mean that the production rule of the form A -> BC is also allowed? Since n ∈ T*, can n be empty ...
1
vote
0answers
19 views

Show that the class of CFLs is not closed under NOPREFIX operation

Define $$\mathrm{NOPREFIX(A)} = \{w \in A \mid \text{ no proper prefix of $w$ is a member of $A$}\}$$ Show that the class of CFLs is not closed under NOPREFIX operation Please hint me.
3
votes
1answer
26 views

Pumping Lemma for CGF question

I'm going through a pumping lemma for a proof that: the language $B = \{a^nb^nc^n \mid n\ge 0\}$ is not context free The first case considers when both v and y contain only one type of alphabet ...
0
votes
1answer
35 views

How to show that there is an equivalent context-free grammar

How can I show that for every context free grammar G, there is an equivalent context-free grammar that has production rules with these forms only: $C→x $WV or $C → λ$, where $x$ is a terminal and $W$ ...
3
votes
1answer
29 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
37 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 ...
1
vote
2answers
801 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
56 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
17 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
328 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
44 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
942 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
13 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
25 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: ...
0
votes
0answers
21 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
23 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
18 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
10 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
8 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
56 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
29 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
58 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
28 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
15 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
48 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
42 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 ...