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)

1
vote
1answer
19 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 ...
1
vote
1answer
22 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
46 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 ...
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
56 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
41 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. ...
1
vote
2answers
26 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
67 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 ...
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 ?
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
16 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
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
36 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
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.
0
votes
1answer
55 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 ...
0
votes
1answer
41 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 ...
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

Is my LL(1) parse table correct?

I have the following Grammar: ...
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
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
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
1answer
54 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
27 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
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$ ...
0
votes
2answers
46 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 ...
2
votes
1answer
41 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 ...
1
vote
1answer
45 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
30 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, ...
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
0answers
52 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
3answers
32 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 ...
0
votes
1answer
40 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
20 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
32 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 ...