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
2answers
19 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
62 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
9 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
18 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
12 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
26 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
14 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
10 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
19 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
32 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
28 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
33 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
48 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
28 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
23 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
18 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
21 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
16 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
9 views

Is my LL(1) parse table correct?

I have the following Grammar: ...
0
votes
0answers
8 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
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
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
34 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
26 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
52 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
19 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
42 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
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 ...
1
vote
1answer
43 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
26 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
49 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
30 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
30 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 = ...
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 ...
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
59 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 ...
1
vote
1answer
47 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: ...
0
votes
1answer
17 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
57 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. ...