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

A proof question involving a regular set and a context free language

Claim: Let $L \subseteq \Sigma^*\{\#\}\Sigma^*$ be a context-free language, where $\# \notin \Sigma$. Suppose that for each $x \in \Sigma^*$, $\{y|x\#y \in L\}$ is finite. Then $\{y|\text{ for some } ...
1
vote
1answer
512 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
16 views

First and Follow for the Context Free Grammar

I am trying to understand how to calculate first and follow for given rules Let's say here are two grammars. They are quite unusual so I am not sure if I made any mistakes. ...
-2
votes
1answer
33 views

proof that $L=\{a^{n}b^{n^{2}} | n\ge0\}$ is not context free language [on hold]

I need help to prove that $\mathcal L=\{a^{n}b^{n^{2}} | n\ge0\}$ is not context free language using the pumping lemma. thanks.
0
votes
1answer
27 views

Prove that $\mathcal L=\{a^ib^jc^k|i+k=j\}$ is context-free

Prove that $\mathcal L=\{a^ib^jc^k|i+k=j\}$ is context-free I am trying to prove it without to build a pushdown automaton First I tried to look which words are in $\mathcal L$, ...
0
votes
0answers
22 views

Best resources for learning about regular and context free languages

I would like to train myself when it comes to finding out if a language is regular or context free. I would be grateful for pointing what are the best places/books for training.
2
votes
1answer
42 views

Is the complement of a given language context-free?

I have a problem with finding out if the complement of language L is context free. $L = \{ ww : w \in \{a,b\}^{*} \wedge \text{ }w \text{ number of }a\text{'s in }w \equiv \text{number of }b\text{'s ...
2
votes
1answer
33 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 ...
2
votes
3answers
10k views

Question regarding Context Free Grammar exercises

I'm working on the exercises in "An Introduction to Formal Languages and Automata" 4th Ed textbook by Peter Linz. Since there are too few answers given in the back of the book, I wasn't able to check ...
0
votes
1answer
39 views

How can I check that the language of one context-free grammar is a subset of a second context-free grammar?

Could you explain me, how can I check, that the language of first context-free grammar (G1) is a subset of the language of second context-free grammar (G2). G1 and G2 are two LL(1) grammars with ...
0
votes
0answers
35 views

Regular and context free language

Let $A$ be a set represented by a regular expression $0^*1^*$ and let $B=\{0^n1^n\mid n\geq 0\}$. It is known that $A$ is a regular language, while $B$ is a context-free language. I understand that ...
1
vote
1answer
431 views

Right-Linear Context Free Grammars

Following is a problem that I have no idea how to solve. I'd appreciate someone showing me how to solve this problem. A CFG is right-linear if each production body has at most one variable, and ...
2
votes
2answers
74 views

formal languages - why is this regular?

I'm studying for a test on formal languages and automata. I came upon the following question (translating, so i apologize for the non-formal english): $L_1$ is the language composed of all words ...
6
votes
2answers
8k views

Determining Ambiguity in Context Free Grammars

What are some common ways to determine if a grammar is ambiguous or not? What are some common attributes that ambiguous grammars have? For example, consider the following Grammar G: $S \rightarrow ...
0
votes
0answers
23 views

Context free grammar language question

I am new to the site. I am quite confused about how to solve the following questions on context free grammars. The first question asks to give the production rules for $a^nb^n | n \geq $ which is ...
1
vote
3answers
41 views

context free grammar accepted and generated language problems

I'm having problems completing the following questions, I am able to attempt them but don't know if they are correct. Any help would be much appreciated. Answer the following questions for a context ...
1
vote
1answer
685 views

Eliminating Epsilon Production for Left Recursion Elimination

Im following the algorithm for left recursion elimination from a grammar.It says remove the epsilon production if there is any I have the following grammer ...
2
votes
2answers
26 views

Prove that if $\mathcal L$ is context-free so $\mathcal L_{\text{even}}$ is context-free

Let $\mathcal L$ be a language. Denote by $\mathcal L_{\text{even}}$ the language consisting of all words in $\mathcal L$ whose length is even. Prove that if $\mathcal L$ is context-free over the ...
2
votes
1answer
645 views
0
votes
1answer
38 views

How would I find the Context Free Grammar for the complement of L = {a^n | n>= 0}? The alphabet is {a}.

I am being asked to complement a language similar to $L = \{a^n\mid n \ge 0\}$. Then construct a context free grammar for that. As I understand, the complement of this is $L' = \{a^n\mid n \lt 0\}$. ...
1
vote
1answer
76 views

How to draw DPDA for language $L = \{a^ncb^{2n} | n \geq1\}$over the alphabet $\Sigma =\{a,b,c\} ?$

An exercise problem $:$ Give a deterministic PDA for the language $L = \{a^ncb^{2n} | n \geq1\}$over the alphabet $\Sigma =\{a,b,c\}$.Specify the acceptance state. My attempt $:$ Grammar of given ...
0
votes
1answer
47 views

Is $L=\{o^{i}1^{j}o^{j}1^{k}o^{k}1^{i} | i,j,k>0\}$ a context free language?

I need some help in finding and proving (by the pumping lemma or by building a grammar) if $L=\{o^{i}1^{j}o^{j}1^{k}o^{k}1^{i} | i,j,k>0\}$ is a context free language. thanks!
0
votes
1answer
25 views

Describe this language (Context Free Grammar).

Below we have a BNF grammar defined by grammar G(N, T, P, S), N={S, C}, T = {a, b, c} and set of productions rules are: S -> S a S b S | S b S a S | C S | S C | Epsilon C -> c C | Epsilon Epsilon - ...
0
votes
1answer
17 views

Context Free Grammar for unsigned real numbers

Construct Context-free Grammar for unsigned real numbers with coma. Each number has the same number of digits before the decimal and after decimal. Example: 0,0; 0090,1117; 1,9; are correct, but ...
1
vote
2answers
28 views

Context Free Grammar for integers

Construct Context-free Grammar for integers. Integer can begin with + or - and after that we have non-empty string of digits. Integer must not contain unnecessary leading zeros and zero should not be ...
1
vote
1answer
38 views

Is $L=\{o^{i}1^{i}o^{j}1^{i} | i,j>0\}$ a context free language?

I need to find and to prove (by the pumping lemma or by building a grammar) if $L=\{o^{i}1^{i}o^{j}1^{i} | i,j>0\}$ is a context free language. I would like to get some help. thanks!
0
votes
0answers
8 views

Make a translation scheme which removes unnecessary brackets

I have ariphmetic expressions which contain $+$, $*$ and brackets. I need to make a translation scheme which can be combined with syntax analysis and which removes unnecessary brackets from ...
0
votes
1answer
33 views

Pumping lemma for two words that “completely different”

Let $"x"$ and $"y"$ be a words, we will say that two words are "completely different" if for all $1\leq i\leq |x|$ the $i$ letter in $x$ diffrent from the $i$ letter in $y$. Prove that the ...
0
votes
0answers
13 views

context-free-grammar for pushdown automata

I need to build context-free-grammar to this pushdown automata My attempt: $S=A_{03}$ because $q_{\color{blue}0}$ is the initial state and $q_{\color{blue}3}$ is the final state. There are $4$ ...
1
vote
0answers
17 views

Converting CFG to PDA for $S\to aSd|aBd\\B\to bBc|\varepsilon$

I need to build a pushdowm automata for the context-free-grammar $$S\to aSd|aBd\\B\to bBc|\varepsilon$$ My attempt: I'm not sure if my attempt is correct or not.
0
votes
1answer
24 views

In a context-free grammar production rule, how to formally write a production rule $x \rightarrow \text{foo}$ where I don't know what $\text{foo}$ is?

I'm trying to formally describe a production rule $$x \rightarrow \text{foo}$$ in a context-free grammar, but I don't know the value of the right-hand side (only that there is a production rule of the ...
3
votes
1answer
46 views

Free context grammar for $\mathscr{L_1}=\{a^{3n}b^{5n}|n\geq0\}$

I need to bulid a free context grammar for $\mathscr{L_1}=\{a^{3n}b^{5n}|n\geq0\}$ My try: $$S\to N_0|N_1|N_2\\N_0\to \varepsilon\\N_1\to aaabbbbb|N_2\\N_2\to aaaN_1bbbbb$$ I'm not sure if ...
1
vote
1answer
41 views

Prove that two arithmetic grammars generate the same language

In my university's automata theory book it is claimed that the following two arithmetic grammars generate the same arithmetic language but no proof is shown. $G_1=(\{E\}, \{a,+,*,(,)\}, \{E\to ...
1
vote
1answer
26 views

Prove that a given CFG grammer $G$ is equivalent to language $L$

I need help to prove that the given CFG grammar $G$ is equivalent to language $L$: as $S\to 0S1 \mid SS \mid \varepsilon$ and $L=\{w\in\{0,1\}^* \mid \#_0(w)=\#_1(w)\text{ and for any prefix } u ...
0
votes
0answers
23 views

How to find a push-down automata that describes $f_{\sigma}(L)$? (given that $L$ is context free language)

Let it be $L$ a context free language. Definition: $f_{\sigma}(L)$={$w:σw∈$$L$}. Need to find a push-down automata $M'$ so that $f_{\sigma}(L)$=$L(M')$. Ok, so here is my idea for ...
0
votes
1answer
21 views

Free context grammar for $\mathscr{L_2}=\{0^i1^j2^k|i,j,k\geq0,i+j=2k\}$

I need to bulid a free context grammar for $\mathscr{L_2}=\{0^i1^j2^k|i,j,k\geq0,i+j=2k\}$ My try: Let denote $T_{x}$ for $k=x$ $$S\to T_{0,1}|T_2\\T_{0,1}\to\epsilon|002|112|012\\T_2\to ...
1
vote
1answer
39 views

Prove that if you can derive w from α in n steps, it's possible with n left-derivations as well

My university's automata theory book claims that the following claim can be proved by induction but it doesn't bother showing the proof. I've tried to prove it myself but I got stuck at the ...
1
vote
1answer
21 views

Analysing a context-free grammar

Let: $$S \to AC \mid BC\\ A \to aAb \mid aA \mid a\\ B \to aBb \mid Bb \mid b\\ C \to Cc \mid c$$ I need to find if: the word $aabbbcc $ is in the grammar, and if so to write a very left series, ...
1
vote
1answer
16 views

There are substrings that are never cut by a smallest grammar.

Define a substring of a string $s$ to be compressible if $|E| = 2$ and the number of non-overlapping occurences $\#_s E$ of $E$ in $s$ is $\geq 3$, or $|E|\gt 2$ and $\#_s E \geq 2$. E.g. $s = a^6 ...
0
votes
0answers
14 views

Levenshtein distance approach to smallest grammars.

Let $G$ be a smallest grammar for a string $s$. Consider the operations: $\text{app}(k,c)=$ append a terminal $c$ to rule $k$. $\text{exp}(k, j)=$ expand recursively rule $j$ and append to $k$ ...
1
vote
1answer
21 views

Context-free language, computability theory

I want to show that the following language is not context-free: $$\{a^nb^m\mid0\leq n\leq m^2\}$$ I tried the word $w=a^kb^k$, but it does not work, because I can't show that for every possible ...
1
vote
0answers
20 views

Context free grammar L={$a^{m}$ $b^{n}$ $c^{k}$| n,m,k >= 0, n>= m+k}

Write a context free grammar for the following: $$L=\{a^{m}b^{n}c^{k}\mid n,m,k \ge 0, n\ge m+k\}$$ I am having some trouble writing the above cfg from the language. So far I have: $$\begin{align*} ...
1
vote
0answers
19 views

Chomsky Normal Form Transformation

I've been struggling a bit with creating the Chomsky normal form derivation of a grammar that I have been given The grammar in question is: $S \to BB \mid 0A0 \mid 1B1 \\ A \to C \\ B \to S \mid ...
1
vote
1answer
18 views

Proving this language is non context-free

How can I prove that the language $\{ab^kab^kab^k\subset \{a,b\}^* | k \geq 0\}$ is non context-free? I've tried applying the pumping lemma but can't write a proof without considering multiple ...
1
vote
1answer
26 views

Cocke-Younger-Kasami (CYK) Proving a word is in a language

Using CYK algorithm I need to figure out whether the word abbabb is a word of the language of the following grammar. I think I have completed the problem correctly but I'm not sure, I'm hoping ...
0
votes
1answer
21 views

How to write a grammar that accepts the language formed by strings $e^{3n} f g^{2n} h$?

$e^{3n}\: f \: g^{2n}\: h$ n ∈ ℕ∪{0} For Example: fh eeefggh eeeeeefggggh I am stuck at the $e^{3n}$ and $g^{2n}$ part. This is what I have so far: ...
0
votes
0answers
17 views

Conversion of CFG to Chomsky Normal Form

I have the following question I have answer for the first one as S->C1S C1->C2A C2->a S->C2A ...
0
votes
1answer
24 views

Pumping lemma for context free. How do I define the string 'w' and define cases?

I am new to the pumping lemma for context free grammars. I have read books and researched online about the pumping lemma, however I am finding it difficult to understand the actual concept and how to ...
1
vote
1answer
33 views

How we derive language from grammar by bottom up or any other approach?

Consider a CFG with the following productions. S → AA | B A → 0A | A0 | 1 B → 0B00 | 1 $S$ is the start symbol, $A$ and $B$ are non-terminals and $0$ and $1$ are ...
1
vote
1answer
53 views

Context free Grammar : three small exercices

Hi everybody I want to submit you my work I did on some works and receiving also some help :) Thank you a lot : so here the exercices on which I worked : Ex 1: Prove that the language : ...