-1
votes
0answers
14 views

$L=${$a^n ww^R b^n$ | $ w \in (a+b)^+ $} [duplicate]

I read that $L=${$a^n ww^R b^n$ | $ w \in (a+b)^+ $} is Context free. any hint or idea for draw a PDA or CFG? thanks to all.
-2
votes
1answer
83 views

Why is the language of even-length non-palindromes context-free?

We know $L_1=\{w_1 w_2 \in (a+b)^*\mid |w_1|=|w_2|, w_2 \neq w_1^{\;\mathrm{R}}\}$ is a context-free language. Can anyone help me produce a PDA or give me any hint how I can quickly understand why ...
1
vote
3answers
80 views

Unable to understand an inequality in an application of the pumping lemma for context-free languages

The problem Prove that the language $\qquad L = \{a^n b^j \mid n = j^2\}$ is not context free using pumping lemma. Approach taken by the book To prove such statements, the book takes the ...
-5
votes
1answer
33 views

What is the language generated by the following grammar? [closed]

Could please tell me the language generated by this grammar? S->iS |iSeS|ε
-3
votes
2answers
79 views

Grammar for a language with 1/3 of a's

I have this language: $$ L = \left\{ w \in \{a,b,c\}^* \;\big|\; |w| / |w|_a = 3 \right\} $$ where $|w|_a$ is the number of occurrences of $a$. How can I find a grammar that generates it?
0
votes
1answer
36 views

CFL, pumping lemma

I have difficulty with proving that the language $ L = \{ a^p b^q | p \ge 1 , q \ge 1 , p \ge q^2 \vee q \ge p^2\}$ $ w = uvxyz $ I've chosen word $ w = a^{N^2} b^N $ where $ N $ is a constant ...
1
vote
1answer
93 views

Resolve left-rescursion

Can anybody give me a hint on how to get rid of the left recursion in the following grammar? $$A \rightarrow B \mid a$$ $$B \rightarrow b \mid C \mid D \mid E \mid F \mid G$$ $$C \rightarrow c \mid A ...
3
votes
0answers
43 views

Automatic tool for resolving left-recursion within CFG [closed]

Though facing the fear that someone might not like my question but does somebody know a useful tool to either resolve left recursion or to simplify a context-free grammar automatically ? I need ...
0
votes
1answer
35 views

Is my grammar correct for this context-free language?

$\{a^nb^2a^n \mid n \ge0\}$ I'm studying for my final and I came across this language. I haven't dealt with characters of the same length on opposite ends with something in between. I came up with ...
3
votes
0answers
55 views

Prove or disprove that every $L$ in this class is a CFL iff $L$ is equivalent to a substitution

Let $L$ be a language with every string of the form $(w_i\#)^*$ with $w_i\in\{0,1\}^*$. Set $w'\sim w$ if there is a permutation $\pi_1$ such that $w_i=w'_{\pi_1(i)}$ for all $i$. If additionally ...
2
votes
1answer
58 views

Is there a Context-free grammar for this language?

Is there a Context-free grammar for the following language: $L=\{ x\#1^m|x \in \{0,1\}^* \space and \space the \space m^{th} \space char \space in \space x \space ...
1
vote
1answer
58 views

Prove not context free

How can we prove that: $$ L = \{ w_1\#w_2 \mid w_1 \in w_2;\; |w_2| > |w_1|;\; w_1 , w_2 \in \{0, 1\}^*\} $$ is not context-free? The language defines $w_1$ as a sub-string of $w_2$, and they ...
1
vote
1answer
50 views

How to check ambiguity of a specific grammar

Giving the following Grammar: S → ^ | SaSMSM | SMSaSM | SMSMSa M → b | c ^ means eopsilon. How can i check whether its ambgious or not? My intuition is ...
0
votes
2answers
74 views

Find a CFG for a language

In an assignment I've been asked to find a CFG for $a^x b^y a^z b^w$, where, $x,y,z,w \in \mathbb{N}^+$, $y > x$, $z > w$, and $x+z = y+w$. A hint was given, think of the language as $(a^p ...
3
votes
2answers
260 views

Proving that a word is *not* generated by a context-free grammar

I saw the answer in one of the solutions and I cannot figure out how they got the answer. The question is asked if the word is in the language or not for CNF... How did they get the answer so that ab ...
2
votes
0answers
85 views

Good introductions to Formal Language Theory and Formal Grammars

Does anyone know any good introductions to Formal Language theory and Formal Grammar, that cover the mathematical basis of Syntax and things like context free grammars and pushdown automata. In ...
0
votes
1answer
45 views

a regular language so that $unary(L) \notin $Context Free Languages [closed]

I need a regular language $ L\subseteq \{0,1\}^{*} $ so that $unary(L)$ is not context free. unary of $L$ is defined by: $$unary(L) = \{0^{1x} : x \in L \}$$ Example $L = \{0, 11\} $ $\rightarrow ...
1
vote
3answers
246 views

How to find whether a grammar's language is finite or infinite?

I have this context-free grammar and I want to find out whether its language is finite or infinite. ...
1
vote
2answers
95 views

proving that if $\{w\$w^R | w \in L\}$ is context-free then $L$ is regular [closed]

I am trying to prove this following theorem, can someone help please? Let $L$ be a language over the alphabet $\Sigma = \{ a,b \}$. If $L' = \{ w\$w^R \mid w \in L\}$ is context-free, then $L$ is ...
1
vote
2answers
222 views

Find a context-free grammar for the language $L=\{a^nb^m\mid 2n<m<3n\}$ [closed]

I need to find a context-free grammar for the following language which uses the alphabet $\{a, b\}$ $$L=\{a^nb^m\mid 2n<m<3n\}$$
3
votes
1answer
84 views

Show that the pumping lemmas for context-free and regular languages are equivalent for unary languages

I want to show that for any language $L \subseteq \{ a \}^* $, $L$ satisfies the pumping lemma for context free languages if and only if it satisfies the pumping lemma for regular languages. I know ...
2
votes
0answers
66 views

If $L_1$ is regular and $L_1 \cap L_2$ context-free, is $L_2$ always context-free? [closed]

If $L_1$ is a regular language and $L_1 \cap L_2$ is a context-free language, does it mean that $L_2$ is a context-free language too? I attempted to prove that $L_2$ was not required to be ...
3
votes
1answer
115 views

Prove that context free languages aren't closed under DropMiddle

The question is simple: $\qquad \operatorname{DropMiddle}(L)=\{xy\in\Sigma^* \mid |x|=|y| \land \exists a\in\Sigma\colon xay\in L\}$. Prove that CFL's aren't closed under ...
2
votes
1answer
50 views

Is $L = \{ x \in \{ 0, 1 \}^* : |x| = 2^n $ for some natural number n $\}$ context free?

I was wondering if this language is context-free: $L = \{ x \in \{ 0, 1 \}^* : |x| = 2^n $ for some natural number n $\}$ I know that this language is not regular because it fails the pumping lemma ...
0
votes
2answers
77 views

Proving that context-free languages are closed under inserting symbols [closed]

This is a theoretical computer science question, regarding the proof of whether or not context-free languages are closed under an operation. This means basically that any context-free language which ...
0
votes
1answer
29 views

Construct context free grammar from language

I have been starting to learn about CFGs and PDAs and have gotten familiar with the simple stuff. I have been able to construct CFGs for simple languages but this question is more specific: $\lbrace ...
0
votes
1answer
51 views

If neither $L_1$ nor $L_2$ are context free then is $L_1 \cup L_2$ also not a context free language? [closed]

If two regular languages $L_1$ and $L_2$ are both not context free languages then is $L_1 \cup L_2$ also not a context free? I am aware that if $L_1$ and $L_2$ are context free languages then the ...
3
votes
2answers
104 views

Defining a context-free grammar for $\{w \in \{0, 1\}^* : \#_0(w) = \#_1(w)\}$ [duplicate]

I have a language where each string in the language has even amount of $0$'s as $1$'s (e.g., $0101$, $1010$, $1100$, $0011$, $10$ are all in the language). I was hoping to define a context-free ...
1
vote
1answer
40 views

Proving a language is not a regular language but a context free language [duplicate]

I have the languages $L_1$ and $L_2$ such that $L_1 = \{a^nba^n :n \in N\}$ and $L_2 =\{a,b\}^*\setminus L_1$. I want to prove that $L_2$ is not a regular language. I know that to prove that $L_2$ is ...
2
votes
1answer
95 views

Context-free grammar for $L = \{a^n : n\leq2^{20}\}$

I want to find a context-free grammar for $L = \{a^n : n\leq2^{20}\}$. There's one for sure. I approached it by two ways and both seemed dead end. One was to set a limit during the production of the ...
2
votes
0answers
40 views

What kind of structural features of strings can be described by regular grammars?

Context-free grammars, as well as other types of grammars, can naturally associate structure with the strings of the defined language, for example tree structures in the case of context-free language. ...
2
votes
1answer
78 views

CFL not closed under intersection while Turing Decidable are

It makes me wonder that despite of (CFL) being a subset of Turing Decidable languages, Turing Decidable is closed under intersection while CFL is not. Does not Turing Decidable engulf all CFLs?
3
votes
2answers
113 views

Complexity of CFG grammar for a regular language

I know that each regular language can be generated by a CFG. This makes, in one sense at least: context-free languages more general than regular languages. Are there known results about the ...
5
votes
1answer
92 views

How to find a Deterministic PDA for an intersection of languages

There are two languages, $\qquad L_1 = \{w\in\{a,b\}^*: N_a\leq N_b\}$ and $\qquad L_2=\{w\in\{a,b\}^*: N_b\leq 2N_a\}$ where $N_a$ means the number of occurrences of $a$ in the string $w$. Same ...
0
votes
2answers
84 views

Is $a^{n+m}b^{n}c^{m}$ context free?

Language: $ L = a^{n+m}b^{n}c^{m} $ As per a recent test I gave, this language is not context free. However, I think it is. Corresponding Grammar: $ X \rightarrow aXY \space |\space \epsilon $ $ ...
0
votes
0answers
17 views

Unambiguous Context free Grammar [duplicate]

I was reading through Context Free Grammar, and I came across ambiguous grammar. If the language produced by CFG has more then 1 parse tree, then CFG is an ambiguous grammar. Is there any way by which ...
2
votes
1answer
87 views

Is the language of words with as many a's in the first as b's in the second part context-free?

Is $L = \{ W_1W_2 \mid W_1,W_2 \in (a+b)^* , N_a(W_1) = N_b(W_2)\}$ context free? Can we construct an NPDA for the language? There is a book here that claims $L$ is not CF (without any elaboration), ...
1
vote
2answers
223 views

Closure of CFL against right-quotient with regular languages

Let $A/B$ = $\{ w \mid wx \in A$ for some $x \in B \}$. Show that if A is context free and B is regular, then $A/B$ is context free. My interpretation of this is is that we need to show that if ...
1
vote
1answer
116 views

Kleene star closure of a context free grammar

I have this question about closure of a context free grammar, and if someone can check my answer and see if it makes sense, and if not, what is missing, I would be very grateful. Give an ...
3
votes
2answers
183 views

How to get 2-state PDA for CFG?

I'm studying for my Computing languages test and there's one idea I'm having problems wrapping my head around, as far as I know for any Context Free Grammar (CFG), we can design a 2-state Pushdown ...
3
votes
1answer
117 views

If $L$ is CFL and $\overline{L}$ is CFL, then is L regular?

I've seen in previous exams that professors marked the theory as correct: If $L$ is CFL and $\overline{L}$ is CFL, then L is regular. I just don't see how this would work. How would we prove ...
1
vote
1answer
49 views

Is the following language context-free? $L= \{a^nb^m| m\geq2^n\}$

Is $L=\{a^nb^m|m\geq2^n\}$ a context-free language?
0
votes
1answer
135 views

Is this language context free?

In a recent test, I was asked to recognize if the below language is context free: $\qquad\displaystyle L = \{0^{n+m}1^{n+m}0^m \mid n,m \geq 0\}$ I think it is context free, and can be accepted by ...
4
votes
2answers
344 views

Is $a^n b^n$ an artificial language or does it occur in the real world?

The classic example of a context-free grammar is $a^nb^n$. That is, $n$ occurrences of $a$ followed by an equal number of occurrences of $b$. Do such forms occur in the real world? Can you provide an ...
1
vote
0answers
35 views

Is this theorem about left-factored grammars correct?

I am working on CFG grammars, LL grammars in particular and I encountered the following theorem in the slides of presentations written by my professor: A CFG grammar cannot be left-factored if all ...
1
vote
1answer
165 views

Is L= $\{ww \mid w \in \{a,b\}^*\}$ context-free? [closed]

Let $L = \{ww \mid w \in \{a,b\}^*\}$. In other words, each word of $L$ is some string repeated twice (some string concatenated with itself). Is the language $L$ context-free?
6
votes
1answer
182 views

Can this CFG be written into an equivalent LL(1) grammar?

I have the following CFG which I suspect cannot be rewritten to one which is LL(1): $S \rightarrow \epsilon\ |\ aSbS\ |\ bSaS\ |\ cSdS\ |\ dScS$ I've thought about it for a while, and can't seem to ...
2
votes
1answer
265 views

Is $\{a, b\}^* \setminus \{ww \mid w \in \{a,b\}^*\}$ context-free?

Define the language $L$ as $L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}$. In other words, $L$ contains the words that cannot be expressed as some word repeated twice. Is $L$ context-free or not? ...
3
votes
1answer
83 views

Looking for a contex-free grammar for the following language

I want to derive a context free grammar for the following language on alphabet $\Sigma=\{a,b\}$: $\qquad\displaystyle \{ xax'yby'z \mid x,y,z\in\Sigma ^*, |x|=|x'|, |y|=|y'|, |z|=|x|+|y|\}$ I am ...
-1
votes
1answer
53 views

Relative complement of a Non CFL to CFL

Let $L$ be a given Context Free Language over the alphabet $\{a,b\}$. Now consider $$L_1=L-\{xyx\ |\ x,y\in\{a,b\}^*\}$$ I know that $\{xyx\ |\ x,y\in\{a,b\}^*\}$ is not Context Free (by using pumping ...