Tagged Questions

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.

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: ...
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 ...
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 ...
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 ...
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?
1answer
14 views

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 ...
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 ...
1answer
9 views

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 | ε, ...
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 ...
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 ...
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 ...
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 ...
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 ...