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
2answers
500 views

Context free grammar $L=\{a^ib^jc^k|j=i+k-2\}$

$L=\{a^ib^jc^k|j=i+k-2\}$ This expression surprise me a lot and put me into deep thinking. what i am doing by solving the expressions: ...
0
votes
1answer
74 views

What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon and unit-production

What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon and unit-production (i.e., of type $A \rightarrow \epsilon$ and $A \rightarrow a$) to ...
0
votes
3answers
831 views

is this language context-free? a tricky one

Is this language context-free? $$L = \{a^nb^nc^{2n} \mid n \ge 0\}$$ It's tricky in my opinion because I know that $a^nb^nc^n$ is not context-free, but can I determine from this that $L$ is not ...
0
votes
0answers
14 views

converting grammar into LL(1)

I have a following CFG: $$K\rightarrow A|K\wedge A$$ $$A\rightarrow L|L\vee A$$ $$L\rightarrow x|\neg x A$$. I would like to convert it into LL(1). I know that I should remove: (hidden) left ...
1
vote
1answer
948 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
1answer
14 views

CFG production rules for multiple CFG's

I have the following 2 part question of which I can do the first part but am having trouble understanding the question for the second part. The first part asked for the production rules for $L_1=(a^nb^...
0
votes
1answer
15 views

Determine whether a language is regular/context free/nither

Let $$L=\left\{w\in\{a,b,c\}^{\ast}\Bigg\vert \exists \sigma_1,\sigma_2\in\{a,b,c\}\text{ s.t } \#_{\sigma_1}(w)\ne \#_{\sigma_2}(w)\right\}$$ Determine whether $L$ is regular, context free of ...
3
votes
1answer
47 views

Identify inherently ambiguous languages

Which of the following languages is/are inherently ambiguous languages? $L_1=\{a^nb^nc^m|m,n\geq0\}\cup\{a^nc^c|n\geq0\}$ $L_2=\{a^nb^nc^m|m,n\geq0\}\cup\{c^mb^na^n|m,n\geq0\}$ My attempt: A ...
3
votes
1answer
843 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 ...
0
votes
1answer
17 views

Context Free Grammar number of b's < double the number of a's

I need to build a context-free grammar for $\{a^ib^j \mid j < 2i\}$ So far I have $$\begin{align*} &S\to aSB\mid ab\mid a\\ &B\to bb\mid b\mid\varepsilon \end{align*}$$
0
votes
1answer
21 views

Which of the following string have two or more parse trees?

Consider the following ambiguous grammar: $S→A|BC$ $A→aAC|B$ $C→bCc|c$ $B→aBb|\in$ Which of the following string have two or more parse trees? $aaabbbbbcc$ $aaabb$ $aabb$ None of these My ...
0
votes
1answer
409 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, ...
0
votes
0answers
14 views

Find the classes of $L_1=\{w|n_a(w)|n_b(w)=n_c(w)\}$ and $L_2=\{wxw^R|w,x\in(0,1)\}$

$L_1=\{w|n_a(w)|n_b(w)=n_c(w)\}$ $L_2=\{wxw^R|w,x\in(0,1)\}$ My attempt: $L_2$ seems regular since it's finite. $L_1$ is DCFL since we can identify strings of $L_1$ using single stack, first we ...
0
votes
1answer
13 views

Find the classes of given languages?

Consider the following statements $L_1 = \{wxw^R \mid w∈(a,b)^*, x∈c\}$ $L_2 = \{wy \mid w,y∈(a,b)^*\}$ $L_3 = \{zwz \mid w∈(a,b)^*,z∈\{a\}\}$ $L_4 = \{wxw \mid w∈(a,b)^*,x∈\{c\}^*\}$ Find the ...
0
votes
0answers
9 views

Prove that for any PDA there is another PDA that accepts exactly the same language bu has only one POP state.

Prove that for any PDA there is another PDA that accepts exactly the same language but has only one POP state. My attempt: Let the counter example $L=\{wcw^R|w\in(a,b)^*\}$ and string of $L$ is $...
0
votes
1answer
11 views

Possible strings of Kleene star of $L = \{a^nb^n|n≥1\}$

Consider the following CFL. $L = \{a^nb^n|n≥1\}$ Then which of the following string can be accepted by the kleene star of the language. $aaabbb$ $aabbaaabbab$ $abbaab$ $λ$ My attempt: The ...
0
votes
1answer
15 views

Is given statement decidable or undecidable?

A given non-terminal A in a given grammar CFG is ever used in the generation of word.-Decidable/undecidable? My attempt: It should be decidable problem, We can solve this problem using membership ...
0
votes
1answer
9 views

Find a Context-Free Grammar for this Context-Free Language

$$ L = \{w_1w_2 : w_1, w_2\, \in \, \{a,b\}^*, w_1 \ne w_2\} $$ So far I have produced this grammar which will produce a string of odd length which follows that $w_1$ and $w_2$ wouldn't be equal. $$ S ...
1
vote
0answers
8 views

Every LL Grammar is not ambigious

An LL grammar is a formal grammar that can be parsed by an LL parser, which parses the input from Left to right, and constructs a Leftmost derivation of the sentence (hence LL, compared with LR parser ...
0
votes
0answers
14 views

Non-Deterministic Push Down Automata popping when only the start symbol is in the stack.

I'm confused about NPDA, specifically about popping. if I had an automata that allows a lambda transition to a popping state that doesn't pop the start symbol what happens? Does it halt? To better ...
1
vote
1answer
12 views

An algorithm to decide if a context-free language like $L_1$ and a regular language like $L_2$ have common members

A context-free language (CFL) is a language generated by some context-free grammar (CFG). A regular language (also called a rational language) is a formal language that can be expressed using a ...
1
vote
1answer
23 views

Consider the language $L_1=\{a^pb^qc^r \mid p,q,r>0\}$ and $L_2=\{a^pb^qc^r \mid p,q,r\geq0 \space\text{and}\space p=r\}$

Consider the language $L_1=\{a^pb^qc^r \mid p,q,r>0\}$ and $L_2=\{a^pb^qc^r \mid p,q,r\geq0 \space\text{and}\space p=r\}$, then which of the following statements are true? $L_1\cup L_2$ is a ...
0
votes
1answer
16 views

Prove/disprove that language of complement of $L=\{a^mb^n|m\neq n \space, m,n\geq1\}$ is context free over alphabet $\{a,b\}$?

Prove/disprove that language of complement of $L=\{a^mb^n|m\neq n \space, m,n\geq1\}$ is context free over alphabet $\{a,b\}$? My attempt : Using pumping lemma $L=\{a^mb^n|m\neq n \space, m,n\...
0
votes
2answers
28 views

Context-Free Grammars: How to understand substitution rules

I am at a bit of a loss when it comes to understanding how to apply substitution rules for checking if a string is accepted / rejected for a given context-free grammar (CFG). Suppose I have been ...
1
vote
0answers
16 views

If $G$ is $LL(k)$, then $L(G)$ is a deterministic context free language.

In formal language theory, a context-free language (CFL) is a language generated by some context-free grammar (CFG). For every grammar, If the correct production can be deduced from the partially ...
-1
votes
1answer
22 views

CFG and Automata regular language and dFA questions

I have the following CFG questions which I am having a hard time getting my head around, I don't have any answers for them so I have no way of knowing if ive done them right or not (even though im ...
2
votes
1answer
77 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
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 ...
0
votes
1answer
27 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
1answer
35 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)$ ...
2
votes
1answer
41 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
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. ...
0
votes
2answers
648 views

Using the Pumping Lemma to Prove $L = \{a^ib^jc^k \mid i < j < k\}$ is not Context-Free

I want to use the Pumping Lemma to prove that $$L = \{a^ib^jc^k \mid i < j < k\}$$ is not context-free. I think I have the intuition, but I don't know how to prove it. Help?
2
votes
1answer
35 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
29 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
33 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
30 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 ones....
5
votes
2answers
45 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
22 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
10 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
56 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
18 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 X|...
1
vote
1answer
29 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
30 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 ...
1
vote
1answer
47 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
37 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
15 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 ...
0
votes
0answers
33 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 ...