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

Grammar generator for the Knight (Chess)

I'm trying to build a regular grammar to generate the valid movements for the knight. I'm using (U)p, (D)own, (L)eft, (R)ight to represent each of the components of the movement. I already have a NFA ...
2
votes
1answer
69 views

How many words are there in a finite context-free grammar in Chomsky normal form?

Given a CFG $G$ written in CNF with $|V|$ variables and $|T|$ terminals, what's the upper bound of the number of words in $L(G)$ if it is finite? Specifically, the Chomsky normal form requires that ...
0
votes
1answer
25 views

Prove that there exists an equivalent grammar in Chomsky Normal Form like $G'$ such that $G'$ has at most $(K-1)|P|+|T|$ production rules

A context-free grammar (CFG) is a set of recursive rewriting rules (or productions) used to generate patterns of strings. A CFG consists of the following components: a set of terminal symbols, which ...
1
vote
0answers
20 views

Rightmost derivation word aaaccb

I have got these context free grammar: $S \implies aSA | a \\A \implies Ab|c$ The goal is find rightmost derivation of word $aaaccb$ a draw derivate tree, which corresponding with this derivation. ...
2
votes
1answer
31 views

Turing Machine Diagram, one Solved Problem ?!

The following Diagram Gets binary number $x$ and produce $x+1$. complete it: the book solution is says first line is the answer. any hint or idea for completing this TM?
1
vote
1answer
27 views

relation on Languages of one finite machine !?

I adopted this question from 2013 Final Entrance Exam on CS. We have Finite Machine $M$ and Languages $L_1$ to $L_4$ as depicted in following picture: The question is which of the $A$ to $D$ ...
0
votes
0answers
27 views

is this grammar ambiguous? and what is the recursive inference, the leftmost derivation and the parse tree for the word abcddd?

first question is, is this grammar ambiguous? how can i show that is there a way? and second question is what is the recursive inference, the leftmost derivation and the parse tree for the word ...
0
votes
1answer
31 views

Give a context-free grammar that generates the language

Give a context-free grammar that generates the language: $\{a^i b^j c^k d^h \mid i, j, h \geq 0, k>0 \text{ and } i+j \leq h\}$ This is what I've done so far: $S \rightarrow aSb \mid bSc \mid ...
0
votes
1answer
27 views

Is it possible for a subset of a non-context free language to be context-free?

For example, if I have a non-context free language of B, is there such a context free language A such that A is a subset of B? I have been thinking of examples but am unable to think of any valid ...
5
votes
2answers
42 views

Can a regular grammar be ambiguous?

An ambiguous grammar is a context-free grammar for which there exists a string that has more than one leftmost derivation, while an unambiguous grammar is a context-free grammar for which every valid ...
0
votes
1answer
18 views

accepted language notation for CFG for recurring 1's and 0's

Hi I often have trouble with the notation when having to write the accepted language for a finite automata or CFG. Right know I have a CFG that generates groups of any number of 1's followed by any ...
0
votes
0answers
7 views

What is the instruction for the following PDA?

I don't understand why there is a push(a,X,a) but then there is no pop - a instruction.
2
votes
2answers
47 views

Prove that L is a sub-language of the CFG G by using induction. (CFG,Induction,School)

i am asking for help with a question from a course in Logic im reading at university. I am aware that this type of question is frequently asked here(i have looked at alot of other questions/answers) ...
1
vote
1answer
15 views

Constructing CFG for $L=\{a^ib^jc^i,\ i,j\ge 0\}$

I'm trying to construct a grammar for the following language $$L=\{a^ib^jc^i,\ i,j\ge 0\}$$ My try: $$G=\left(V=\{S,X,Y\},\Sigma=\{a,b,c\},R,S\right)$$ where the rules are \begin{align*}S&\to ...
1
vote
1answer
28 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
27 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
1answer
38 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 ...
1
vote
1answer
32 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
46 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 ...
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 ...
3
votes
2answers
36 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
0answers
29 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 ...
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 ...
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?
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 ...
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 ...
3
votes
1answer
32 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
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?
2
votes
2answers
26 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
48 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
51 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 ...
2
votes
1answer
31 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
34 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 ...
0
votes
1answer
43 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 ...
1
vote
1answer
31 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$
0
votes
1answer
94 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 ...
1
vote
1answer
26 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$, ...
0
votes
1answer
39 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
38 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. ...
2
votes
1answer
50 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
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 ...
2
votes
2answers
83 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
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 ...
0
votes
1answer
30 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
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 ...