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

Is the following language context-free?

I need to show whether the language $L_2$ is context-free or not where $L_2$= $\overline{L}$ such that L= { $a^nb^m$ : 0 ≤ n ≤ m ≤ 2n }. I am able to show that L is context-free , S­> aSb | aSbb | ε, ...
0
votes
1answer
23 views

Finding a Regular Grammar

so I have to find a regular grammar to generate the following sets: $(1)$ $\{aa, ab, ac\}$ $(2)$ $\{ab^n,ba^n\mid n\ge 0\}$ $(3)$ $\{ab^{2n}\mid n\ge0\}$ I'm wondering if anyone can check my ...
2
votes
0answers
27 views

Difference of a regular language and a context-free language

I know that given the context-free language L and the regular language R, the language L \ R is context free. But what about R \ L ? My attempt is as follows: R \ L = R $\cap$ $\overline{L}$ We ...
0
votes
0answers
24 views

Language generated by context free grammar

I studied about CFG and one point confused my mind. If rules of grammar given like that; $S \to AB\ |\ C$ then continue with rules of $A$, $B$, $C$ or other nonterminals. Should we define $L(G)$ ...
1
vote
1answer
34 views

Find an LL(2) grammar for the following language

The question asks to find both an LL(1) and an LL(2) grammar for the following language {𝑎^𝑚 𝑏^𝑛 𝑐^𝑚+𝑛 | m,n ϵ N} I have an LL(1) grammar like so ...
3
votes
2answers
32 views

subsets of non regular language

I know that there are many languages that are context free but not regular like $\{a^n b^n :n>0\}.$ But I want to know if every context free but non-regular language has infinitely many non-regular ...
0
votes
1answer
13 views

regular languages ,context free grammer.

I know that if a language is regular then it is context free. and i know also that the class of regular languages are closed under intersection. Now, Lets say we have two languages that are not ...
1
vote
1answer
811 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
21 views

Convert a PDA to a CFG

My professor doesn't do a very good job at explaining the process of converting a PDA to a CFG. Can someone help explain it? The way I see it (but it produces wrong results) is each production is ...
0
votes
1answer
390 views

Understanding how to convert a PDA to a CFG

Given a PDA, initialized with $\#$ on the stack, and with accepting states $q_a, q_b, q_c$ and the following transitions: (current state, stack head, input character, replacement for old stack head, ...
2
votes
1answer
792 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 ...
3
votes
2answers
31 views

Prove that $(()())\in P$ (the set of balanced paranthesis) and $))(() \notin P$

Given the recursive definition of $P$ (the set of balanced paranthesis): Base: $() \in P $. Recursive step: if $w \in P$ then: $$(w) \in P$$ $$()w \in P$$ $$w() \in P$$ And I have to prove that ...
2
votes
1answer
24 views

Proving that everything in a language can be generated by a grammar

Suppose $L=\{w \in {a,b}^* \colon \#b(w) = \#a(w) \}$, the language of all strings with an equal number of occurrences of $a$ and $b$ in all possible arrangements. Furthermore, this language can be ...
1
vote
0answers
16 views

Verify correctness of this PDA

I'm trying to construct a PDA for the language $\{a,b\}$ where there are the same number of $a$'s as $b$'s. This is what I have, but I'm skeptical on the correctness. Can anyone verify?
0
votes
1answer
16 views

Context free grammar over { a^n * b^(n+3) | n >= 0 }

Context free grammar over { a^n * b^(n+3) | n >= 0 } So far I have this, but I don't think it's entirely correct ...
2
votes
1answer
31 views

Context-free language

Given $L= \lbrace w \in \lbrace 0, 1 \rbrace^* \ : \ |w|_0 \leq |w|_1 \leq 2 |w|_0 \rbrace$, where $|w_0|$ is number of zeros in $w$. Is $L$ context-free?
3
votes
1answer
31 views

Existence of context-free grammar over {0,1} alphabet

Is there a context-free grammar $G$ for which $L(G) = \lbrace w \in \lbrace 0,1 \rbrace^{*} : \exists a,b \in \lbrace 0,1 \rbrace^{*} \wedge w = aba \wedge |a| = |b| \rbrace$? This question could be ...
2
votes
2answers
19 views

Ambiguous grammar $S\to ABA$, $A\to aA|\varepsilon$, $B\to bB|\varepsilon$

I need to show that: $$S \rightarrow ABA $$ $$A \rightarrow aA|\varepsilon$$ $$B \rightarrow bB|\varepsilon$$ is ambiguous and find an equivalent unambiguous grammar. I can't seem to see how this is ...
1
vote
2answers
43 views

Using Pumping Lemma to prove a language not regular

I'm currently stuck on a problem were I'm asked to look at a language and prove whether or not it is a regular language or something else such as context-free. I've been given the example: ...
1
vote
1answer
44 views

How to check if a language is regular

I'm currently studying a formal languages & automate module on my course and I have been asked to answer the following question: Which of the languages below are regular? If the language is ...
0
votes
1answer
22 views

How to describe this Context Free Grammar?

I've been having a really difficult time in describing the following Context Free Grammar S → SS | T T → aTb|ab I understand that it must start with an ...
0
votes
1answer
42 views

Regular grammar with parity

Give a regular grammar that generates the set of strings over {a, b, c} with an odd number of occurrences of the substring bc. How can you limit the number of recursions for a regular grammar to be a ...
2
votes
1answer
22 views

Regular grammar that generates a set of strings with an odd number of occurrences of a substring

This is for a homework assignment. The prompt is: Give a regular grammar that generates the set of strings over {a, b, c} with an odd number of occurrences of the substring bc. I've been stuck ...
0
votes
1answer
31 views

Create a formula for order of parenthesis

I am stumped at creating a formula (for a coded math problem evaluator) that finds what is within the parenthesis. It gets tricky when you have () within ...
0
votes
1answer
18 views

What is flaw on my proof to identify any string of $L_2$ using single stack?

Consider the following languages: $L_1=\{a^nb^mc^{n+m}:m,n≥1\}$ $L_2=\{a^nb^nc^{2n}:n≥1\}$ Which one of the following is TRUE? Both $L_1$ and $L_2$ are context-free. $L_1$ is context-free while ...
1
vote
1answer
30 views

Which grammar generates the language: $L = \{a^i b^j d^k | i, j, k ≥ 0 ∧ j < k\}$

I am unsure, how can the second answer be the right one - and why not the first one? Can some one explain it step by step? Why i think the first answer is right: $aS \to aSA \to aAAd \to abddd$
1
vote
2answers
1k views

$w$ such that it contains at least 3 ones, is my approach to the CFG right?

So I was trying to solve the CFG, $$\{w \in (0,1)^* \mid w \text{ contains at least three 1's}\}$$ My approach: I decided that a string can begin with a $0$, end with a $0$, it may begin with a ...
0
votes
1answer
87 views

Stronger Pumping Lemma for Context Free Languages

Hi Math Stack Exchange, Taking a class in automata theory, and having real trouble proving the following strong automata theorem for context free languages (from Sipser, Problem 2.37): If L is a ...
0
votes
1answer
31 views

Identify language of given PDA?

Consider the transition diagram of a PDA given below with input alphabet $Σ =\{a,b\}$ and stack alphabet $Γ = \{X,Z\}. Z$ is the initial stack symbol. Let $L$ denote the language accepted by the PDA. ...
1
vote
1answer
25 views

How to identify context free language?

Consider the following context-free grammars$:$ $G_1: S → aS|B, B → b|bB$ $G_2: S → aA|bB, A → aA|B|ε, B → bB|ε$ Which one of the following pairs of languages is generated by $G_1$ and $G_2$, ...
1
vote
1answer
30 views

Subtracting a context-free language from a regular language

I have the language $L=\{a, bb\}^*-\{a^ib^i|i\geq1\}$ and I have to show that $L$ is context-free. The first language is Regular, if I'm not mistaken, and the second is a well known context-free ...
1
vote
1answer
27 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 } ...
0
votes
0answers
20 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. ...
0
votes
1answer
29 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$, ...
2
votes
1answer
47 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
34 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
11k 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
44 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
41 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
458 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
82 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 ...
7
votes
2answers
9k 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
31 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
48 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
37 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
689 views
0
votes
1answer
42 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
100 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
49 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
28 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 - ...