The tag has no wiki summary.

learn more… | top users | synonyms (1)

0
votes
0answers
7 views

Eliminating left recursio of a grammar

I would like to create a grammar in which each binary operation is represented by one parent node with 3 children (operand1 op operand2). However I´m creating the productions such as the other of ...
0
votes
1answer
263 views

Context free grammar to pushdown automata…

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

Context free grammar for AN

I need to write Context free grammar for describing moves in a game of chess using the Algebric Notation. Can anyone help me get started. f.ex. how do I write this for this move: Bb5 Bd7.
1
vote
1answer
33 views

Prove that $\{ww^R\#ww^R\}$ is not context free

I need to prove that $L = \{ww^R\#ww^R \; | \; w \text{ is in } \{a,b\}^*\}$ is not context free. I have tried using the pumping lemma for this. For $w=a^pb^pb^pa^p\#a^pb^pb^pa^p$. I have two cases ...
1
vote
1answer
8 views

Isn't $L=\{ww|w \in \{0,1\}^*\}$ a Non Deterministic Context Free Language?

My book says that it is not a Non Deterministic CFL. If $ww^R$ can be a N-CFL, then why not the one in the question? I think it might be a printing mistake, not sure.
3
votes
0answers
16 views

Show that minimal CFG is undecidable (Sipser 5.36)

Question: Say that a CFG (context-free grammar) is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{\text{CFG}}$ = $\{\, \langle G \rangle$ | $G$ is a ...
1
vote
0answers
24 views

If syntax with Backus-Naur form [closed]

I'm doing a "parser" with the BNF syntax. My program should get as input the condition of an "if" statement, where, if the user enters the following condition: ...
0
votes
1answer
21 views

Context-free grammar for an expression

how to find context-free grammar for generating language $$J={\{ba^mc^na^ma^nb}\;| n\ge1, m\ge1\} $$ I have already solved problems with constructions like $a^mc^mc^na^n$, but how to appropach the ...
1
vote
0answers
24 views

Why is $a^nb^n|n\geq1$ not regular and $a^nb^n|n\leq {10^{10}}$ regular?

I've heard somewhere that since the latter is bounded, it is regular. Can anyone explain me what a bound actually means? And if the latter is regular, then how would you write the regular expression ...
0
votes
1answer
31 views

Obtaining a grammar CFL

Let b(n) denote the binary representation of n >= 1, leading zeros omitted. For example, b(5) = 101 and b(12) = 1100. Let $ be another symbol not in {0,1}. Suppose we reverse the first numeral; that ...
1
vote
1answer
51 views

Can 2 items be added/taken away from a stack in push down automata at once?

Here is a language and 2 ways (I hope) of representing it with a PDA. Can I use the notation (b,a $\to$ ee) or anything of the like, to take away 2 items from the top of a list at once? Such as I ...
2
votes
0answers
21 views

Collapsing adjacent states in a grammar

I am trying to write a program which can induce a grammar from an example of the code(really more of a corpus than an example). I'm ignoring the decision problem, because I am doing two things that ...
1
vote
1answer
101 views

Is a lanaguage is cfl

I've been asked to decide whether a given language is CFL. If yes, I should find the grammar that creates her, and if not, I need to prove it (with the pumping lemma). The given language is the ...
1
vote
1answer
43 views

Context free grammar to NFA

I've been given an exercise to solve which goes as follows: generate an NFA from the given CFG, S -> AB | c A -> aAb | c B -> bBa | c Now correct me if I'm wrong, but if this language has an NFA it ...
1
vote
2answers
33 views

How to break down a problem while constructing a CFG for a language?

A problem I came across was: Design a CFG for the language $\{a^ib^jc^k\,|\,i=j+k \}$ The solution I came up with : $S\rightarrow aSc\,|\,S_1$ $S\rightarrow aS_1b\,|\,\epsilon$ It took ...
1
vote
2answers
433 views

Every Regular Language is a Context Free Language

How do I show that every regular language is a context-free language? I've been told to construct a Context-Free Grammar by Induction on the number of operators in the regular expression; but I'm ...
1
vote
1answer
35 views

Prove that $L=\{a^nb^nc^md^m \mid m,n >=0\}$ is context free language

I'm trying to write the grammar of this language, in order to prove that it is CFL but I'm stuck because m or n could be 0. The language is: $L=\{a^nb^nc^md^m \mid m,n >=0\}$ . If they were ...
0
votes
1answer
24 views

$L_1 =(a^nb^n)$ and $L_2 =(a^nb^{2n})$. Is $L_1 \cup L_2$ DCFL?

I think that since $a^nb^n$ is not regular (applied pumping lemma), so is $L_2$. Therefore, $L_1 \cup L_2$ is not cfL. Is that correct?
0
votes
0answers
28 views

Forming the alphabet of a grammar

What does {nA|A->x element of P} mean when defining an alphabet ? Note that A is subscript
0
votes
1answer
37 views

Prove language is not context free with pumping lemma

$$L=\big\{a^{3k}b^{2k}c^k\in\{a,b,c\}^* | k>= 0\big\}$$ I'm trying to use the pumping lemma to prove this language is not context free. so far I have... $p=$ Pumping lemma $S = a^{3p}b^{2p}c^p$ ...
0
votes
2answers
50 views

Construct a PDA to accept the language

construct a PDA that accepts the language: a) $L_1 = \{ a^k b^k c^i \mid k,i \ge 0 \}$ my answer is : $$\begin{align*} &S\to AA\\ &A\to abc \mid ab \mid c \mid \lambda \end{align*}$$ b) ...
0
votes
2answers
55 views

How to design a Context-Free Grammar and Pushdown Automaton for the following language:

How would you design a context-free grammar for the following language? $\{p^n \ r^m \ p \ \ b^{m+n} \ \ r^2 ∣ m,n\geq 0\}$ Derive a Pushdown Automaton that accepts the same language as the CFG. ...
1
vote
0answers
20 views

Prove or disprove: $L^2$ context free implies $L$ is context free.

Clearly we have to disprove this. But I am finding it hard to prove it. I was trying in following way: Considering any non context free language $L$. I was trying to prove that $L^2$ is context free ...
0
votes
1answer
25 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?
0
votes
1answer
33 views

Construct context free grammar which generates following language $\{wcw^R\in\{a, b, c\}^*\mid w\in\{a, b, c\}^* \}$

(i) $\{wcw^R\in\{a, b, c\}^*\mid w\in\{a, b, c\}^* \}$ So far I have $E \to EcE$ $E \to a$ $E \to b$ $E \to c$ But I'm new at this and feel I'm miles away from a finished answer
0
votes
0answers
18 views

Is the string in $L(G)$?

I have to write an $O(n^3)$ algorithm to determine whether a given string $w=a_1 a_2 \dots a_n $is in $L(G)$, where $G=(N, \Sigma ,P, S)$ is a context-free grammar in Chomsky normal form. Could you ...
2
votes
2answers
34 views

prove the complement of a language is context free

Language $L=\{a^n b^n c^n : n\geq1\}$ is not context free and it is known (please correct me if I am wrong). What i would like to know is will the complement of this language be a context free, if ...
0
votes
1answer
20 views

For $\sum = \{ 0,1 \}$, $A$ has strings which contain a $1$ in their middle third, and a $B$ which contain two $1$'s in their middle third.

Language $A$ can also be represented as, $$A = \{ uvw \mid u,w \in \sum^*\text{ and, }v \in \sum^* 1 \sum^*\text{ and, }|u| = |w| \ge |v| \}$$ Language $B$ can also be represented as, $$B = \{ uvw ...
0
votes
0answers
8 views

How do I know how many times to repeat a replacement when generating a grammar?

My textbook discusses Context Free Grammars, and provides the following rules: A -> 0A1 A -> B B -> # The resulting string is 000#111. Shouldn’t it just be 0#1? My steps: A 0A1 0B1 0#1 I’m ...
1
vote
0answers
13 views

Induction for quantified statement with two discrete parameters

Given a quantified statement ∀n, n>0 (∃x, x>2k | x=2k+n) ( a subset of the natural numbers) This can logically this can be deduced as valid; however, I wish to use induction. Specifically I would ...
0
votes
1answer
21 views

context free grammar production rules

I am working with context free grammars and have a question concerning the production rules. I have read that the rules are formalized as pairs (α,β) ∈ R. The natural language rules that I am working ...
0
votes
1answer
31 views

How to Determine which language is guaranteed to be a deterministic Context-Free Language

I'm struggling with figuring out which one of these languages is guaranteed to be a DCFL, i have two languages to choose from and the word guaranteed is throwing me off. Here are the two languages: ...
2
votes
2answers
3k views

Pushdown automata for the language $\{ w001w^\text{R} : w = \{0,1\}^* \}$

I'm trying to make a PDA that accepts the language $\{ w001w^\text{R} : w = \{0,1\}^* \}$ by empty stack. (Here $w^\text{R}$ denotes the reverse of the string $w$.) Our stack symbol s $\#$. I've come ...
1
vote
1answer
711 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, ...
1
vote
0answers
55 views

Pumping Lemma for Context Free Languages: Is this language CFL?

I am learning for the first time the Pumping Lemma for CFL, and I thought I understood how it works until I came across this example: "Show that $L = \{a^m b^m c^n \mid m \leq n\}$ is not a CFL." My ...
1
vote
1answer
197 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
20 views

Is it possible to build an Pushdown Automata for an Ambiguous Context-Free Grammar?

Say I have the following grammar: $$S \to \epsilon \mid [S] \mid (S) \mid SS$$ This grammar is ambiguous as both the following parse trees yield the empty string $$S \to \epsilon$$ $$S \to SS \to ...
1
vote
1answer
416 views

Finding a Context Free Grammar for this language

(Paraphrasal of problem 2.48a in Sipser - Introduction to the Theory of Computation, 3rd ed.) The language $L$ consists of all binary strings with a $1$ somewhere in the middle third of the string, ...
1
vote
0answers
25 views

Converting a long CFG to Chomsky Normal Form

I know there's a lot of examples on here, although I just cant seem to get this one, it seems significantly harder than any examples I've seen, the grammar is: S-> ABAC | BaA A-> Aa | BAbC | ...
1
vote
2answers
252 views

Live Variables in Context Free Grammar

A variable $A$ in a context free grammar $G= \langle V, \Sigma, S, P\rangle$ is live if $A \Rightarrow^* x$ for some $x \in \Sigma^*$. Give a recursive algorithm for finding all live variables in a ...
0
votes
0answers
15 views

find an algorithm to find terminal string [duplicate]

I would like to know an algorithm which, given a cfg, finds those variables A that derives atleast one terminal string. I can show it by giving some production rules and say that particular variable ...
1
vote
2answers
25 views

Pumping Lemma proof

We have a language $$ L = \{\text{w element of } \{a,b\}^* \mid \#(a,w) = \#(b,w)^2 \} $$ where $ \#(a,w) $ means the number of letters $a$ in $w$ I would like to show that this language is not ...
0
votes
1answer
67 views

CFG and PDA for w1#w2

Looking for a Context Free Grammar and Push Down Automata to describe a language made of two words, separated by a #, where the first words is not equal to the second word. For this example, we can ...
0
votes
1answer
38 views

Language of words $1^k$ where $k$ is not a prime

Is the language $$\{1^k:k\text{ is not a prime number}\}$$ a context free language? If, not how can I prove this using the pumping lemma for context free languages?
0
votes
1answer
18 views

If $R$ is a regular language and both $L - R$ and $L ∩ R$ are context-free then $L$ is context-free

If $R$ is a regular language and both $L - R$ and $L ∩ R$ are context-free then $L$ is context-free I have to prove or give a counterexample. I know the closures properties of CFL, however, this ...
3
votes
1answer
142 views

Challenge on Some Language and PDA

Suppose We have Some language as follows: $L_1=\{w^* | w=x \text{ and } x \in \Sigma^*\}$ $L_2=\{ww^R ww^R | w \in ( \Sigma + \Sigma)^*\}$ $L_3=\{w | w=xy, x,y \in \Sigma^*, y \text{ is a ...
0
votes
1answer
32 views

Push Down Automata that recognizes language

I'm struggling on how to use the stack for this push down automata problem. The problem is to design a PDA that recognizes the language: $$A = \{a^ib^{2i}|\,i>0\}$$ So, we will be pushing a's onto ...
-1
votes
1answer
40 views

Proving that CFG generates a language

I need to construct a CFG for the language consisting of even length palindromes with the same number of a's and b's and then prove that it generates that language. This is the CFG I got: S→ abba | ...
3
votes
2answers
4k 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
2answers
128 views

CFG for language

I can't find CFG for this language. $N = \{w ∈ \{0, 1\}^* \mid \text{w contains more } 1\text{s than }0 \text{s}\}$ Basically, it is much easier when order is set (for example, $1$s come after $0$s) ...