The tag has no wiki summary.

learn more… | top users | synonyms (1)

0
votes
0answers
11 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
0answers
7 views

Am I converting this Context Free Grammar correctly?

My homework problem is to convert this context free grammar into Chomsky Normal Form. ...
0
votes
0answers
9 views

Chomsky Normal Form for Integer Recognition

If I have the following CFG, which is just the regex [0-9]+: ...
0
votes
0answers
10 views

Show L is not context free using the CFL pumping lemma

I am trying to use the pumping lemma to show this language is not context free: $L = a^nb^{n+1}c^{2n} : n \ge 0$ So I took $z = a^mb^{m+1}c^{2m}$ where $|z| = 4m+1 > m$. We can decompose $z = ...
0
votes
0answers
8 views

Describe this language that is generated by Context Free Grammer

Describe this language that is generated by Context Free Grammer S -> SS S -> XXX X -> aX| Xa| b
1
vote
1answer
17 views

How is this derivation possible in a context-free grammar?

Suppose we have the rules: $R \rightarrow XRX | S$ $S \rightarrow aTb | bTa$ $T \rightarrow XTX | X | \epsilon$ $X \rightarrow a | b$. My textbook says that $T \stackrel{*}\implies T$ is ...
0
votes
1answer
22 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
0answers
11 views

Chomsky Normal Form Details

I'm converting a CFG to CNF and there are some details that I'm unsure of. I know the form is A-->BC A-->a Is a transition such as S-->AA|... ...
0
votes
1answer
21 views

Prove a language is Context Free

I am working on the following problem and I do make a little progress. Let me state the question first: Prove that the set of strings consisting of $a$'s and $b$'s with an equal number of $a$'s and ...
0
votes
1answer
21 views

Can any Language that is generated LL1 Grammar is regular.?

I have a question is every language generated by LL(1) grammar is regular? I know that every regular language can be generated by LL(1) grammar.
0
votes
1answer
13 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
0answers
27 views

Context-free languages

Is the following language context-free? $\{ w \in \{a,b,c\}^* : (\#_a(w) - \#_b(w)) \cdot \#_c(w) = \#_b(w)$ and all c's are encountered before any a$\}$. $\#_a(w)$ = amount of a's in w Thanks in ...
0
votes
1answer
26 views

Context Free Grammar for natural numbers

this is the problem: Generate a Context Free Grammar for the language $L_1 := \{{a^nb^3c^n | n\in\mathbb N}\}$ I'm not so sure about my solution, is this correct?: $ G=(\sum,V,S,P)$ $\sum : = ...
1
vote
1answer
12 views

Creating the production for a CFG

I have to create the productions for a CFG that follows $$\{a^ib^jc^k : j = i + k\}$$ I can get close to the answer. I found $$\begin{align*} &A\to aAb \mid B\\ &B\to bBc \mid \epsilon ...
0
votes
2answers
29 views

Find a CFG for L = { a^nb^m : n != m }

This question is upcoming for my midterm and I can't figure it out. My professor broke it down in two statements (n>m) and(m>n) and left us at that. Find a context free grammar for $L = \{ a^n b^m : ...
1
vote
1answer
23 views

There is a sequence of operations on grammars of a string that strictly decreases the size of grammars down to the smallest grammer.

I'm trying to figure out the smallest grammar problem, which yes I know is impossible since it's such a hard problem, but humor me for a sec. Let $g$ be a smallest grammar for the string $s$ over the ...
1
vote
0answers
26 views

Are there useful combinatorial constructions of grammars?

By grammar I mean a formal language grammar such as $$ A \to aaBa \\ B \to bB | a $$ You can define a tree recursively as, letting $T= $ set of all trees, as $T = \bullet \times SEQ(T)$, where ...
0
votes
0answers
16 views

Eliminate Useless Productions

How do I eliminate useless productions from the grammar: $S \rightarrow a|aA|aaB|abC$ $A \rightarrow aB|\lambda$ $B \rightarrow Aa$ $C \rightarrow cCD$ $D \rightarrow ddd|aC$
0
votes
1answer
14 views

Eliminating Unit Productions

Eliminate all unit-productions from the grammar: $S \rightarrow abA\:|\:A\:|\:B$ $A \rightarrow B\:|\:ba\:|\:aBA$ $B \rightarrow A\:|\:aa\:|\:aA$ An article I was reading said that a unit ...
1
vote
1answer
16 views

Producing CFG for a language

The language of palindromes over {a,b} whose length is a multiple of 3, I am clueless as to how you would attempt this.
0
votes
1answer
22 views

Context Free Grammar for the language?

Give CFG for $L = \{w \in \{a, b\}^{*} | n_{a}(w) \leq n_{b}(w) ≤ 2n_{a}(w)\}$, here $n_{x}(w)$ is the number of occurrences of x in w. I came up with $S-> aSb | bSa| b$ but not working as ...
2
votes
1answer
32 views

Is well formed XML context-sensitive grammar?

Solution Copy language is noncontracting, so it's context-sensitive. Look at https://en.wikipedia.org/wiki/Noncontracting_grammar for transforming noncontracting grammar to explicitly $\alpha ...
0
votes
1answer
6 views

The necessary conditions in a proof by pumping lemma for CFG

Do we need to cover all the cases or just one of them? For instance, for $L = a^ib^jc^id^j$, the proof is uvw can't contain both a and $c$ and $b$ and $d$, but we don't cover all the cases, for ...
1
vote
1answer
46 views

Is the language $L=\{ww^f|w\in \{0,1\}^*\}$ CFL?

Where $w^f=$flipping the bits of w. For example, $(0010)^f=1101$, $(010111)^f=101000$ I tried to prove that $L$ is not CFL using the pumping lemma, with no succeed. In addition, I need to prove ...
1
vote
1answer
18 views

Is it possible to make a PDA for $\{ ww : w \in \{ 0,1 \}^* \}$?

Consider the language $L = \{ ww : w \in \{ 1,0 \}^* \}$. I know it's easy to make a PDA for $\{ w w^\text{R} : w \in \{ 0,1 \}^* \}$ where $w^{\text{R}}$ is the reverse of $w$, but I can't think of ...
0
votes
2answers
61 views

Express $\{w\mid w \text{ contains at least two } 1\text{'s}\}$ in CFG

Let $\Sigma = {0, 1}$. Write CFG that generates the following language {w | w contains at least two 1’s} I'm not really sure how to write a CFG that generates a language, so this is my attempt... ...
1
vote
0answers
20 views

Create context-free grammar for $\{w \mid |w| $ is odd with a 0 in the middle$\}$

I need to find a CFG where the word length $|w|$ is odd. Plus there must be a $0$ in the middle. In a previous exercise I had to specify a CFG only for odd word length. I chose the following: $G = ...
0
votes
2answers
42 views

How do you show that a cfg is ambiguous?

Do we just need to show that we can get a certain string more than in 1 way? S > SSaS|SS|a|epsilon Ex: S > SSaS > aa ...
0
votes
0answers
13 views

Conversion from PDA to CFG

We have the pushdown automata (q) -> a,X/Y1 Y2 Y3 -> (r). and the template for it is [qXx] -> a[rY1y][yY2z][zY3x]. our teacher used another template that was derived from the first one. ...
0
votes
0answers
16 views

Relationship between pushdown automata and CFG

I thought that pushdown automata and CFG were separate things in that one was the graphical expression of the other, but I saw a pushdown automata that uses CFG terms such as epsilon, S, S->1S0, or ...
1
vote
1answer
22 views

How do you insure that from a CFG you get the same number of as and bs?

I can make a CFG that makes sure we can produce any string that has the same number of as and bs, but I can't insure that those strings are the only ones that are produced. S => aS | bS | E The ...
0
votes
1answer
20 views

Proving that a language having a particular CFG grammar is equivalent to a particular L

I think we need to prove that L(G) is a subset of L and then we need to prove that L is a subset of L(G). For the first part, I think we need to say for any w in L(G) we have an even number of as ...
1
vote
1answer
23 views

Particular Problem for Context Free Grammars

Consider the context-free-grammar $G$ defined by productions: $$ S \rightarrow aS\,|\,Sb\,|\,a\,| b $$ Prove by induction on the string length that no string in $L(G)$ has $ba$ as a substring. I ...
0
votes
1answer
27 views

Creating a Push Down Automaton from a Grammar

I have the following grammar, but I'm not sure what exactly it is that it does: $\qquad\begin{align} S &\to S \vee T \mid T \\ T &\to T \wedge F \mid F \\ F &\to p \mid \thicksim p ...
0
votes
1answer
69 views

Context free grammar to pushdown automata…

<expr> −→ <term> | <expr> + <term> <term> −→ <factor> | <term> × <factor> <factor> −→ (<expr>) | b ...
4
votes
1answer
55 views

Proving that a language is not context-free

Given the language $$L = \{ a^p \mid p\, \text{IS NOT prime} \}$$ is $L$ Context free? If not, prove that it's not. May I have some suggestions on how to use the pumping lemma to prove this, ...
0
votes
1answer
23 views

If the language is context free?

i believe intuitively the following language is CF. But there is a book (without more description) that states the language is not CF. If I'm in a wrong way? $L=\{W_1cW_2 | W_1,W_2 \in (a+b)^* W_1 ...
1
vote
1answer
17 views

Left Recursion-Deterministic grammars

I have a question.. Is the rule $$X \to XX|a$$ a left recursive production? To make the grammar deterministic do I have to do the following changes? $$ X \to aX' ,X' \to XX'|\varnothing$$
1
vote
1answer
17 views

Is the language regular or contextfree?

Could you tell me if the language $$L=\{ w \in \{a,b,c\}^*: $$$$\text{there is at least one time the substring abc and none of the symbols a,b,c is repeated three times} \}$$ is regular or ...
1
vote
1answer
17 views

Use closure properties for the language $L=\{a^kb^l:|k-l| \leq 100 \}$

Given the language $$L=\{a^kb^l:|k-l| \leq 100 \}$$ I have to show that $L$ is regular or context free using closure properties. I have done the following: The language is regular. Let $k>l$, then ...
0
votes
0answers
6 views

X->XX|a is it a left recursive production?

I have a question...Could you tell me if the rule $X \to XX|a$ is a left recursive production?
1
vote
0answers
15 views

If L is context-free,is L' also context-free?

It is given that $L$ is context-free with $\Sigma=\{a,b,c,d\}$ and $L'=\{w:w \in L \text{ and } w \text{ contains only the symbols a or b till one point,and the symbols c or d after this point}\}$.Is ...
1
vote
1answer
29 views

find the grammar for the language that contains all and only the words that have the form: $(a … b c (b) (c c) b ) (a (c b) c … a (b) a b)$

Give a context-free grammar for the language,with $\Sigma=\{(,),a,b,c\}$,that contains all and only the words that have the following form: $(a ... b c (b) (c c) b ) (a (c b) c ... a (b) a b)$ ,that ...
0
votes
0answers
19 views

Deterministic Context Free Languages and set operations

Suppose L, S are DCFL. Is co-((co-L) $\cap$ (co-S)) necessarily CFL? I know DCFL are closed under complement but not under intersection. So what really happens with DCFL $\cap$ DCFL?
0
votes
0answers
29 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 ...
1
vote
1answer
39 views

Difficulty finding context free grammar for this language

I'm learning context free grammars from languages. Language ${L=\{{a}^{2i}\,{b}^j\,{c}^k\,|\,3i=j+k, i \gt 0\}}$ My guess is $${S\rightarrow BA}$$ ...
2
votes
1answer
39 views

Context free grammar for language

I'm learning how to generate context-free grammar for a language. $L=\{{a}^i {b}^j {c}^k\, |\,i=j\lor j=k$ Here is how I tried ...
0
votes
0answers
22 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 ...
1
vote
0answers
21 views

parse-tree for the word $x_{1}-x_{2}+x_{3}*x_{4}$

Let $G$ the following grammar with $\Sigma=\{x,+,-,*,/,1,2,....,9\}$ and with start symbol $I$: $$I \to IPI | xD$$ $$P \to +|-|*| /$$ $$D \to 1|2|...|9$$ I have to make the parse tree for the word ...
0
votes
1answer
38 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 ...