The tag has no wiki summary.

learn more… | top users | synonyms (1)

0
votes
0answers
10 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 ...
1
vote
1answer
381 views

Proof that equal-length-concatenation is a context-free language?

If A and B are languages, define A⋄B={xy | x ∈ A and y ∈ B and |x|=|y|}. For example, if A = {00, 101, 111} and B= {1, 11, 00110}, we would have A⋄B={0011}. Show that if A and B are regular, ...
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
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
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

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
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
28 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.
2
votes
2answers
726 views

Construct Context-free Grammar for the Language

Hey so I am currently stuck on a question regarding context free grammars. Here is the question: Construct a context-free grammar for the language L1 = {w1#w2 | w1 and w2 contain the same number of ...
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 ...
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 ...
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 ...
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
17 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
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
2answers
60 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
0answers
12 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
15 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
22 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
2answers
43 views

Construction Types or Type Constructions?

In any (simple) type theory there are base types (i.e. the type of individuals and the type of propositions) and type builders (i.e. $\rightarrow$, which takes two types $t,t'$ and yields the type of ...
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
66 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?
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
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}$$ ...