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
14 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
10 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
11 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
0answers
7 views

Grammar to Chomsky Normal Form [on hold]

I am trying to convert the following crammer into Chomsky normal form but I am having some problems getting the correct result. The Grammar is as follows: S -> abS | aFeD D -> bFDb | bab | e F -> ...
0
votes
2answers
45 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
34 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
38 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
37 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
18 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
21 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
40 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
26 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
17 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
21 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
26 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
30 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
50 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
36 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. ...
-2
votes
0answers
34 views

Formulate an equivalent CFG that is not ambiguous

Given is the following grammar G: S -> SS | T | ab T -> aTb | empty string a) Formulate an equivalent CFG that is not ambiguous. It suffices to give the rules.
1
vote
1answer
29 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
36 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 ...
-1
votes
1answer
28 views

Context Free Grammar(CFG) Generating Strings [closed]

Define a context free grammar and explain how it generates a set of strings? I don't understand the concept of CFG
0
votes
1answer
102 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
129 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
38 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
37 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
77 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
51 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
28 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
104 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
36 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
39 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} = \{ ...
2
votes
1answer
27 views

Concatenation of context free language and a maybe pointless theorem

In our lecture our professor claimed this result: Let $\{1,\dots,k\}$ be an alphabet (or terminals) for the context free grammar $\tau$, $L(\tau)$ is the language generated by $\tau$. Let ...
2
votes
1answer
38 views

Intersection of context-free language and its reversal

I know that intersection of two context-free languages is not always context-free and the following problem: Given two context-free languages A and B, is $A \bigcap B \neq \emptyset$ ? is ...
0
votes
1answer
22 views

Eliminating epsilon-productions in grammar

I am wondering how to eliminate epsilon-productions in grammar: S β†’ S0 S β†’ 1 S β†’ AB B β†’ AC A β†’ Ξ΅ C β†’ Ξ΅ I know that because of ...
0
votes
1answer
36 views

Give context-free grammars for these languages(Need clarification for my answer)

I'm just looking to understand if my justification I wrote makes sense (it might not) in a) b). Note: I'm doing exercises from a textbook which has no solutions I can see. So I can't check my answer ...
0
votes
0answers
32 views

Context-Free Grammars(Clarification on answer)

I'm trying to make sure if i did a) correct. I believe it makes sense, just trying to see if anyone has any suggestions. The grammar ...
0
votes
1answer
158 views

Context free grammar of calculator

Consider a grammar for calculator language. This language consists of all arithmetic expressions that can be evaluated by a calculator, i.e. expressions of the form ...
0
votes
1answer
26 views

Closure properties between 2 languages of different types

Whenever said - The intersection between a Context Free Language and a Regular Language is always Context Free, what is the best logical way to confirm the statement? I have this Chomsky hierarchy in ...
2
votes
1answer
20 views

Concatenation of regular languages.

The concatenation of $L_1$ and $L_2$ denoted by $L_1.L_2$ = $\{uv|u\in L_1\,and\,v\in L_2\}$. If, $$L_1=\{a^n|n\geq0\}\,and\,L_2=\{b^n|n\geq0\}$$ Then why is $$L_1.L_2\neq \{a^nb^n|n\geq0\}$$ I am ...
0
votes
0answers
19 views

Eliminating left recursion of a grammar

I would like to create a grammar in which each binary operation is represented by one parent node with 3 children (operand1 op operand2). However IΒ΄m creating the productions such as the other of ...
0
votes
2answers
89 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.
1
vote
1answer
51 views

Prove that $\{ww^R\#ww^R\}$ is not context free

I need to prove that $L = \{ww^R\#ww^R \; | \; w \text{ is in } \{a,b\}^*\}$ is not context free. I have tried using the pumping lemma for this. For $w=a^pb^pb^pa^p\#a^pb^pb^pa^p$. I have two cases ...
1
vote
1answer
11 views

Isn't $L=\{ww|w \in \{0,1\}^*\}$ a Non Deterministic Context Free Language?

My book says that it is not a Non Deterministic CFL. If $ww^R$ can be a N-CFL, then why not the one in the question? I think it might be a printing mistake, not sure.
3
votes
0answers
66 views

Show that minimal CFG is undecidable (Sipser 5.36)

Question: Say that a CFG (context-free grammar) is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{\text{CFG}}$ = $\{\, \langle G \rangle$ | $G$ is a ...