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
15 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 ...
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 ...
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 ...
3
votes
1answer
48 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 ...
0
votes
0answers
16 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
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
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
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
15 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 ...
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\...
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
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
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
votes
1answer
23 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 ...
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
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
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
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
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 ...
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
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)$ ...
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 ...
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 ...
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
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 ...
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
25 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
17 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
33 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
27 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
51 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: $$\{...