3
votes
1answer
19 views

$L=${$a^nb^nc^n : n \geq 0 $} CFG Recognizing

Suppose $L=${$a^nb^nc^n : n \geq 0 $} and I. $h(L), h(a)=a, h(b)=bb, h(c)=b$ II. $L^R$ III. $L^*$ IV. $h(L), h(a)=a, h(b)=bb, h(c)=a$ Why just I is a CFG and other is not? anyone can help me to ...
1
vote
1answer
38 views

Designing a context free grammar

I have to design a grammar over the alphabet $\sum=(a,b)$, so that $c^a(\alpha)=c^b(\alpha)$ and the second part $c^a(\alpha)\leq c^b(\alpha)$ , where $\alpha$ is a word and $c^a$ and $c^b $ are ...
0
votes
0answers
39 views

Is the language $L = \{0^m1^n: m \neq n \}$ not context free?

I have been trying to prove that this is not a context free language using the pumping lemma for CFLs. I have tried for hours but am not able to prove it. Is it a context free language or not? How to ...
0
votes
1answer
34 views

How to prove not a CFL with pumping lemma?

need to prove using the pumping lemma that $L=\{a^{2N} b^{N} c^M d^N| M,N>=0\}$ is not Context-Free. This is what I have so far: Suppose that L is a CFL. Let p be the pumping length. Choose ...
0
votes
1answer
18 views

how to come up with a solution of finite or infinite language using context free grammer?

I am trying to come up with a solution of finite or infinite language using context free grammer. I have these grammers to find if it's a solution of finite or infinite language ...
0
votes
1answer
133 views

Context free grammar to pushdown automata…

<expr> −→ <term> | <expr> + <term> <term> −→ <factor> | <term> × <factor> <factor> −→ (<expr>) | b ...
0
votes
0answers
34 views

Eliminating Immediate Left Recursion

I understand that in order to eliminate an immediate left recursion from a grammar containing production of the form $A\implies Aα$ I need to replace it by $A\implies βA'$ and $A'\implies αA/∈$ Im ...
0
votes
1answer
41 views

Is this language context free and if it is which grammar generates it?

$$L=\{\, w \in\{a,b,c\}^* :w=a^ib^jc^k, j=\max\{i,k\}\,\}$$ I think I proved it not context-free using pumping lema for CFL, but I'm not sure I'm doing it right. So, if someone knows grammar that ...
3
votes
2answers
115 views

Need Help to convert a grammar into Chomsky Form

I have to convert the following grammar into Chomsky Form $$( \Sigma=\{a,b,c,+\}, \Sigma_Q=\{S,V\},I=S)$$ $$S -> S+S|V$$ $$V -> a|b|c$$ My idea is the following: $$S_0 \rightarrow S$$ $$S ...
1
vote
3answers
182 views

Context free grammar question

i have two context free grammar questions and I don't know how to do them. $$\{(a^n)b(c^n) \mid n >0 \}$$ I'm having trouble with this one because I don't know how to account for $a$ or $b$ not ...
3
votes
1answer
82 views

Prove that Y is not context free.

2.42 Let $$Y = \{w\mid \text{$w=t_1\#t_2\#\cdots\#t_k$ for $k \ge 0$, each $t_i \in 1^*$, and $t_i \ne t_j$ whenever $i \ne j$}\}.$$ Here $\Sigma = \{1,\#\}$. Prove that $Y$ is not context free. ...
1
vote
1answer
100 views

Proving a set is language generated by given grammar

I have grammar $G$ with productions $S\rightarrow aS|aSbS|\epsilon$, and task is to prove that $L(G)=\{w|$every prefix of $w$ has at least $a$'s as $b$'s$\}$ (I'm not sure if translation is correct, I ...
3
votes
2answers
47 views

Injective map, that maps context-free languages to regular languages

Let $\Sigma \neq \emptyset$ be an alphabet. Is there an injective map $f: \Sigma^* \rightarrow \Sigma^*$ such that for every context-free language $L \subseteq \Sigma^*$ the set $f(L)$ is a regular ...
1
vote
1answer
61 views

Generating a context free grammar

How do I generate a context free grammar for a language $$\left\{a^ib^jc^k:i=j\text{ or }j=k,\text{ and }i,j,k\ge 0\right\}\;?$$ Thanks.
3
votes
2answers
125 views

context free grammar problem

$L$ is the context free grammar over $\{a, b\}$ $S \rightarrow aSb \; | \;bR \; |\;Ra$ $R \rightarrow bR \;|\;aR\;|\;\epsilon$ Briefly describe this CFG with English sentences and prove your ...
0
votes
2answers
52 views

context free grammar design

Design a context free grammar and PDA for the following language. $$\Sigma = \{0,1\},\qquad L = \left\{uv \mid u \in \sum^{*} \;v\in \sum^{*}1\sum^{*} \text{ with }|u| \geq |v| \right\}$$ I'm not ...
1
vote
0answers
24 views

What do you call a mildly-context sensitive grammar in which the LHS must appear in the grammar spec?

For instance: $$ S \rightarrow aAbAb \\ aAb \rightarrow AAa \\ A \rightarrow Aa | a $$ $aAb$ is alright to have on the left-hand side since it occurs directly in the grammar spec. Further indirectly ...
1
vote
1answer
50 views

Are these two context free grammars equivalent?

Let Σ = {a,b}. A CFG for the language {a^nb^m | n > 2m} can be written as: S-->aaSb S-->A A-->aA A-->a Would it be equivalent to write this CFG as: ...
1
vote
1answer
76 views

Decidability Turing Machine Problem

$L=\{G|G$ is a context free grammar over ${a,b}$ and $L\{G\}$ contains at least one string $w$ such that the number of $a$'s in $w$ is a multiple of $5\}$ Show that L is decidable by ...
2
votes
1answer
48 views

Proving non CFL with pumping lemma

I can't seem to figure out how to prove this as not a CFL: $$\left\{x^{a}y^{b}\mid a=kb\space\text{for some positive integer k}\right\}$$ I've tried a bunch of "s"'s to pump such as $a^{2p}b^{p}$ ...
4
votes
2answers
339 views

Push down automata problem

Informally describe the Nondeterministic PDA that generates: $$\{x\#y\ \mid x,y\in\{a,b\}^{*}\text{and}\space x\ne y\}$$ My initial plan was to use nondeterminism to go through each character before ...
3
votes
1answer
71 views

Context free language problem

I'm trying to find an unambiguous context free language for the ambiguous language: $$S\rightarrow AB$$ $$A\rightarrow Ba| b$$ $$B \rightarrow aA|b$$ I understand the language makes up of strings ...
4
votes
1answer
53 views

Does the following transformation preserve context-freeness?

I encountered this problem involving manipulating a context-free language. Let $L$ be a context-free language. Define $L^{\#} = \{ x : x^i \in L$ for every $i=0,1,2,...\}$. Is $L^{\#}$ always ...
2
votes
2answers
3k 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 ...
1
vote
1answer
133 views

Proof of the pumping lemma for Context-Free Languages

I have a doubt concerning the proof of the pumping lemma for context-free languages. The pumping lemma for context-free languages is stated as follows: If $A$ is a context-free language, then ...
0
votes
3answers
629 views

Are these languages context free or not?

$L_1=\{a^nb^mc^nd^m \mid m,n >0\}$ $L_2=\{a^nb^mc^md^n \mid m,n >0 \}$ $L_3=\{a^mb^n \mid m+n\text{ is a prime number}\}$ $L_4=\{a^mb^n \mid n=m^2\}$ $L_5=\big\{ww^R\#ww^R \mid w \in \{a,b\}^* ...
0
votes
1answer
134 views

Regular grammar and context grammar problems

If $G$ is not a regular grammar, then $L(G)$ is infinte. If $L^*$ is context free then $L$ is definitely context free. If $G$ is a context free grammar that is language is $L$ (meaning $L(G) = L$), ...
1
vote
0answers
144 views

PDA state diagram with an inifinite languge but with no looping states

For class I'm supposed to create a PDA state diagram that is capable of generating an infinite language with no state q such that q is reachable from the start state, there is no cycle within the ...
6
votes
1answer
1k views

An efficient way to determine if two context free grammars are equivalent?

I'm wondering if there's an efficient way of checking to see if two context free grammars are equivalent, besides working out "test cases" by hand (ie, just trying to see if both grammars can generate ...
2
votes
1answer
162 views

Proof that language is not context-free.

Is this the appropriate way to show that this language is not context-free? Given the language $L$ containing the words $1$, $101$, $101001$, $1010010001$, where each word $L_n$ is of the form ...
1
vote
1answer
57 views

Proving $\{ll^{R}l|l\in\{a,b\}^{*}\}$ is not context free using the pumping lemma

How can I prove, using the pumping lemma for context free languages, that $\{ll^{R}l|l\in\{a,b\}^{*}\}$is not a context free language ? I tried to put $n$ as the pumping lemma constant and chose ...
2
votes
2answers
508 views

Context free languages closure property $\{a^n b^n : n\geq 0\} \cup \{a^n b^{2n}: n\geq 0\}$

I have been working on the following two problems: 1) Given any context free language L, form a new language by taking symbols at the odd positions, i.e. $w=a_1a_2\dots a_n \mapsto w'=a_1 a_3 a_5 ...
2
votes
1answer
158 views

$L=\{\langle G_1,G_2 \rangle|G_{1,2}$ are context free grammars, and the size of $L(G_1) \cup L(G_2) $is a prime$\} \in R$?

Why does the following language $L=\{\langle G_1,G_2\rangle|G_1$ and $G_2 $are context free grammars, and the size of $L(G_1) \cup L(G_2)$ is a prime $\} \in R$? How do I prove it? I didn't come to ...
0
votes
1answer
88 views

Pumping lemma - do I have to show every way to split string to have a complete answer?

In the pumping lemma, we have to split strings into $uvwxy$ (for example). Say the language was $a^n$$b^n$$a^n$$b^n$. We could it this way: $a^r$$a^s$$a^t$$a^u$$b^n$$a^n$$b^n$, with $uvwx$ all ...
4
votes
1answer
148 views

For CFG $G$ and regular expressions $R,S$: To which class does $\{ \langle G,R,S \rangle: L(G) \cap L(R) = L(S) \}$ belong?

I'd really like your help with the following question: For $G$ a context free grammar, and $R$, $S$ regular expressions, To which class does $\{ \langle G,R,S \rangle : L(G) \cap L(R) = L(S) \}$ ...
2
votes
1answer
73 views

A model of computation for co-CFLs?

The context-free languages can be described as the languages that can be generated by a context-free grammar or recognized by a (nondeterministic) pushdown automaton. The context-free languages are ...
0
votes
1answer
247 views

Determining if language is context free

Is {xayb : x,y in {a,b}* and |x|=|y|} a context free language? My natural instinct would be to say that the answer is no, but can someone show me how to prove this?
1
vote
1answer
2k views

Why is this Parsing Expression Grammar left recursive?

I'm trying to get my parser generator to accept this specification. I know that's kind of a programming question, but I figured this was the best place to ask. It's specified as a Parsing Expression ...
0
votes
1answer
50 views

Question about the Smallest Grammar problem.

Is the problem to prove whether or not there exists an algorithm with running time polynomial in the length of the input string $|s|$, or polynomial both in $|s|$ and the size of the alphabet $|A|$ ? ...
0
votes
1answer
202 views

Proving that a grammar generates a language

Since every context free grammar is equivalent to a Push down automaton, to show that a grammar $G$ generates a language $L$, is it sufficient to draw a PDA equivalent to $G$ and then show the PDA ...
0
votes
1answer
292 views

Is it always possible to convert a non-deterministic PDA to a deterministic one?

Is it always possible to convert a non-deterministic PDA to a deterministic one? What is the significance of this observation for the computing power of contex-free grammars?
4
votes
3answers
818 views

What is the CFG of the language that generates all strings over alphabet $\{a, b, c\}$?

The most obvious one that I found was, $$S \rightarrow SSS | A | B | C$$ $$A \rightarrow Aa | \epsilon$$ $$B \rightarrow Bb | \epsilon$$ $$C \rightarrow Cc | \epsilon$$ However, I realize this CFG is ...
3
votes
2answers
5k 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 ...
2
votes
1answer
768 views

Is the language $L = \{a^ib^jc^kd^l : i,j,k,l \geq 0 \text{ and } i + k = j + l\}$ context free language?

Is the language $L = \{a^ib^jc^kd^l : i,j,k,l \geq 0 \text{ and } i + k = j + l\}$ context free language? My initial thought was to prove that it is not a CFL by using Pumping Lemma for CFG with the ...
2
votes
2answers
523 views

Is the language $L = \{0^m1^n: m \neq n - 1 \}$ context free?

Consider the language: $L = \{0^m1^n : m \neq n - 1 \}$ where $m, n \geq 0$ I tried for hours and hours but couldn't find its context free grammar. I was stuck with a rule which can check on the ...