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)

-2
votes
1answer
18 views

Describe briefly the interrelationships that exist between, LRGs, Regular sets and DFAs [on hold]

This question has appeared in a number of papers related to my current module in college. Would anyone be able to answer it? Thanks.
1
vote
0answers
15 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
32 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
18 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
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: ...
0
votes
0answers
16 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
18 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
12 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

Is my LL(1) parse table correct?

I have the following Grammar: ...
0
votes
0answers
6 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
26 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
21 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
49 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$ ...
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 ...
2
votes
1answer
39 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
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
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, ...
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
44 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
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 ...
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 = ...
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
33 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
57 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
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: ...
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
44 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
30 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
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 ...
0
votes
1answer
47 views

Show that this CFG is ambiguous

Let $G=\langle V,T,P,S\rangle$ be the grammar defined by the productions: S-> aB|bA A->a|aS|bAA B->b|bS|aBB where ...
3
votes
0answers
92 views

Converting a pushdown automaton (that accepts by final state) to a context-free grammar

Given the following PDA: $$ P = (\{q, p\}, \{0, 1\}, \{Z_0, X\}, \delta, q, Z_0, \{p\}) $$ where the transition function $\delta$ is given by: $$ \delta(q, 0, Z_0) = \{(q, XZ_0)\} \\ \delta(q, 0, ...
-1
votes
1answer
53 views

$L_{a}= \{w_{1}cw_{2} : w_{1},w_{2} \in \{a,b\}^{\ast}, w_{1} = w_{2}\}$ [closed]

Why the following is not context free? Anyone could describe it for me. $L_{a}= \{w_{1}cw_{2} : w_{1},w_{2} \in \{a,b\}^{\ast}, w_{1} = w_{2}\}$
0
votes
1answer
29 views

Launguages in Discrete Mathematical Structures II

For the grammar $G$ specified, draw a derivation tree for each of the given strings or conclude that the string is not derivable from $v_0$. $G = (V, S, v_0 , \rightarrow ), \\ V = \{v_o, v_1, x, y, ...
0
votes
1answer
108 views

Context Free Grammar and some details [closed]

Why this grammar shows a Context Free and Linear Language, (i.e, not context sensitive or non-context free). S -> SBA | a BA -> AB aA -> aaB B -> b
0
votes
1answer
38 views

Prove the following context-free language is generated by this grammar.

I would like to prove the context-free language $$ \mathcal{A} = \{ w\#x ~:~ w^R \text{ is a substring of $x$ for } w,x \in \{0,1\}^* \}, $$ has the context free grammar \begin{align*} ...
0
votes
1answer
43 views

Prove the following language is context free

I can find many proofs for how a language is not context free using the pumping lemma. But I am not sure how to definitely prove a language is context free. Consider this language: $$\mathcal{A} = \{ ...