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
16 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
41 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
22 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
80 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
102 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
30 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
25 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
68 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
50 views

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

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
292 views

inherently ambiguous languages [on hold]

Why is the second language an inherently ambiguous languages? Could anyone clarify it to me? L={$a^nb^{2n}c:n\geq 0$} $\cup ${ $a^{2n}b^{n}d:n\geq 0$} L={$a^nb^{m}c^p:n\neq m$} $\cup ${ ...
0
votes
1answer
100 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
33 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
34 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
25 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
31 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
20 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
34 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
31 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
113 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
22 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
15 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
43 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
60 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 ...
0
votes
1answer
29 views

Context-free grammar for an expression

how to find context-free grammar for generating language $$J={\{ba^mc^na^ma^nb}\;| n\ge1, m\ge1\} $$ I have already solved problems with constructions like $a^mc^mc^na^n$, but how to appropach the ...
1
vote
0answers
29 views

Why is $a^nb^n|n\geq1$ not regular and $a^nb^n|n\leq {10^{10}}$ regular?

I've heard somewhere that since the latter is bounded, it is regular. Can anyone explain me what a bound actually means? And if the latter is regular, then how would you write the regular expression ...
0
votes
1answer
37 views

Obtaining a grammar CFL

Let b(n) denote the binary representation of n >= 1, leading zeros omitted. For example, b(5) = 101 and b(12) = 1100. Let $ be another symbol not in {0,1}. Suppose we reverse the first numeral; that ...
1
vote
1answer
103 views

Is a lanaguage is cfl

I've been asked to decide whether a given language is CFL. If yes, I should find the grammar that creates her, and if not, I need to prove it (with the pumping lemma). The given language is the ...
1
vote
1answer
62 views

Context free grammar to NFA

I've been given an exercise to solve which goes as follows: generate an NFA from the given CFG, S -> AB | c A -> aAb | c B -> bBa | c Now correct me if I'm wrong, but if this language has an NFA it ...
1
vote
2answers
40 views

How to break down a problem while constructing a CFG for a language?

A problem I came across was: Design a CFG for the language $\{a^ib^jc^k\,|\,i=j+k \}$ The solution I came up with : $S\rightarrow aSc\,|\,S_1$ $S\rightarrow aS_1b\,|\,\epsilon$ It took ...
1
vote
1answer
60 views

Prove that $L=\{a^nb^nc^md^m \mid m,n >=0\}$ is context free language

I'm trying to write the grammar of this language, in order to prove that it is CFL but I'm stuck because m or n could be 0. The language is: $L=\{a^nb^nc^md^m \mid m,n >=0\}$ . If they were ...
0
votes
1answer
33 views

$L_1 =(a^nb^n)$ and $L_2 =(a^nb^{2n})$. Is $L_1 \cup L_2$ DCFL?

I think that since $a^nb^n$ is not regular (applied pumping lemma), so is $L_2$. Therefore, $L_1 \cup L_2$ is not cfL. Is that correct?
0
votes
0answers
30 views

Forming the alphabet of a grammar

What does {nA|A->x element of P} mean when defining an alphabet ? Note that A is subscript
0
votes
1answer
46 views

Prove language is not context free with pumping lemma

$$L=\big\{a^{3k}b^{2k}c^k\in\{a,b,c\}^* | k>= 0\big\}$$ I'm trying to use the pumping lemma to prove this language is not context free. so far I have... $p=$ Pumping lemma $S = a^{3p}b^{2p}c^p$ ...
1
vote
1answer
59 views

Can 2 items be added/taken away from a stack in push down automata at once?

Here is a language and 2 ways (I hope) of representing it with a PDA. Can I use the notation (b,a $\to$ ee) or anything of the like, to take away 2 items from the top of a list at once? Such as I ...
0
votes
2answers
91 views

Construct a PDA to accept the language

construct a PDA that accepts the language: a) $L_1 = \{ a^k b^k c^i \mid k,i \ge 0 \}$ my answer is : $$\begin{align*} &S\to AA\\ &A\to abc \mid ab \mid c \mid \lambda \end{align*}$$ b) ...
0
votes
2answers
63 views

How to design a Context-Free Grammar and Pushdown Automaton for the following language:

How would you design a context-free grammar for the following language? $\{p^n \ r^m \ p \ \ b^{m+n} \ \ r^2 ∣ m,n\geq 0\}$ Derive a Pushdown Automaton that accepts the same language as the CFG. ...
1
vote
0answers
20 views

Prove or disprove: $L^2$ context free implies $L$ is context free.

Clearly we have to disprove this. But I am finding it hard to prove it. I was trying in following way: Considering any non context free language $L$. I was trying to prove that $L^2$ is context free ...
0
votes
1answer
35 views

How to construct a context free grammar that generate following language. $\{a^nb^nc^k \in \{a,b,c\}^* | n,k >= 0\} $

$$\{a^nb^nc^k \in \{a,b,c\}^* | n,k >= 0\} $$ $E \to aEbS $ $S \to c$ I do not know where to go next, or even if this is right at all?
0
votes
0answers
18 views

Is the string in $L(G)$?

I have to write an $O(n^3)$ algorithm to determine whether a given string $w=a_1 a_2 \dots a_n $is in $L(G)$, where $G=(N, \Sigma ,P, S)$ is a context-free grammar in Chomsky normal form. Could you ...
0
votes
1answer
46 views

Construct context free grammar which generates following language $\{wcw^R\in\{a, b, c\}^*\mid w\in\{a, b, c\}^* \}$

(i) $\{wcw^R\in\{a, b, c\}^*\mid w\in\{a, b, c\}^* \}$ So far I have $E \to EcE$ $E \to a$ $E \to b$ $E \to c$ But I'm new at this and feel I'm miles away from a finished answer
2
votes
2answers
43 views

prove the complement of a language is context free

Language $L=\{a^n b^n c^n : n\geq1\}$ is not context free and it is known (please correct me if I am wrong). What i would like to know is will the complement of this language be a context free, if ...
0
votes
1answer
32 views

For $\sum = \{ 0,1 \}$, $A$ has strings which contain a $1$ in their middle third, and a $B$ which contain two $1$'s in their middle third.

Language $A$ can also be represented as, $$A = \{ uvw \mid u,w \in \sum^*\text{ and, }v \in \sum^* 1 \sum^*\text{ and, }|u| = |w| \ge |v| \}$$ Language $B$ can also be represented as, $$B = \{ uvw ...
0
votes
0answers
9 views

How do I know how many times to repeat a replacement when generating a grammar?

My textbook discusses Context Free Grammars, and provides the following rules: A -> 0A1 A -> B B -> # The resulting string is 000#111. Shouldn’t it just be 0#1? My steps: A 0A1 0B1 0#1 I’m ...
0
votes
1answer
25 views

context free grammar production rules

I am working with context free grammars and have a question concerning the production rules. I have read that the rules are formalized as pairs (α,β) ∈ R. The natural language rules that I am working ...
1
vote
0answers
15 views

Induction for quantified statement with two discrete parameters

Given a quantified statement ∀n, n>0 (∃x, x>2k | x=2k+n) ( a subset of the natural numbers) This can logically this can be deduced as valid; however, I wish to use induction. Specifically I would ...
0
votes
1answer
35 views

How to Determine which language is guaranteed to be a deterministic Context-Free Language

I'm struggling with figuring out which one of these languages is guaranteed to be a DCFL, i have two languages to choose from and the word guaranteed is throwing me off. Here are the two languages: ...