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
0answers
12 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. ...
-1
votes
1answer
28 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
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
41 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 ...
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
33 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 ...
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 ...
0
votes
0answers
22 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 ...
0
votes
1answer
26 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$, ...
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 ...
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 ...
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 ...
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!
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 ...
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 ...
1
vote
1answer
38 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 ...
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 ...
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 ...
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 ...
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
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
52 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 : ...
0
votes
1answer
33 views

Writing a Context Free Grammar for a language with multiple strings in the language

I have an interest in computing and want to learn more about the actual theory behind it. Context Free Grammar plays a part and I am quite fascinated by it all. However, I came with a language that ...
0
votes
2answers
30 views

What is the language of following CFG?

A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals. $$S → aS \mid A \\ A → aAb \mid bAa \mid \epsilon$$ Which of the following ...
1
vote
1answer
32 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 ...
0
votes
0answers
14 views

Ambiguity regarding definition of ambiguous grammar

I was having a confusion regarding the definition of ambiguous grammar.Suppose for all strings possible there is a unique left derivation and a different but unique right derivation tree.Now the ...
0
votes
1answer
27 views

DCFL are closed under Intersection with Regular Languages?

Let $L_1$ be a regular language, $L_2$ be a deterministic context-free language and $L_3$ a recursively enumerable, but not recursive, language. Which one of the following statements is false? $L_1 ...
0
votes
1answer
34 views

Prove that the class of Turing Decidable Languages is strictly larger than class of Context Free Languages

Prove that the class of Turing decidable languages is strictly larger than the class of context free languages. (Give a language that is Turing decidable, but which violates the pumping lemma for ...
0
votes
1answer
16 views

If I rewrite a grammar to remove ambiguity, will it remain equivalent to the original one ?

For example, I have this grammar E → E + E | E * E | a | b | c It is ambiguity for the case: a * b + c, which have 2 parse tree: E => E + E => E * E + c => a * b + c and E => E * E => a * E + E ...
0
votes
0answers
43 views

Construct an NPDA for the following language: L = {a^nb^m | n>= 0, n!= m}

How we've learned is to first construct a CFG, and then use that to construct the npda. Our end goal is a transition graph. The language is $L = ${${a^nb^m | n>= 0, n!=m}$} We can think of ...
1
vote
0answers
22 views

why is automaton with a queue is more powerful than an automaton with a stack?

what is the logic behind this statement that with the use of queue the automaton becomes more powerful , is it that in a queue , we may do operations from both the ends as compared to a stack so it is ...
0
votes
0answers
13 views

Is $\left ( 0+1 \right )^{\ast }-\left \{ www : w \in \left \{ 0,1 \right \}^{\ast } \right \}$ context-free?

Is $\left ( 0+1 \right )^{\ast }-\left \{ www : w \in \left \{ 0,1 \right \}^{\ast } \right \}$ context-free? If it is what is a grammar generating it?
0
votes
0answers
14 views

Grammer to CNF - Wierd problem

Given G = ({S,A,B,C,D,E}, {0,1}, P, S) where P is S --> 0A0 | 1B1 | BB | DE A --> C B --> S | A C --> S | ε D --> 0 | DE E --> EE Convert to CNF: I came up with the following but i'm stuck.... i'm ...