The tag has no wiki summary.

learn more… | top users | synonyms (1)

0
votes
0answers
9 views

Pumping lemma for context free language

I am proving that $a^n b^m$ is not context free if $gcd(n,m)=1$. I am using pumping lemma. I have chosen the string as $a^{p!} b^{p+1}$. I couldn't proceed with that. I chose another string as $a^p ...
0
votes
1answer
9 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
0answers
14 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 ...
0
votes
1answer
23 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
2
votes
2answers
26 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
16 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 ...
0
votes
1answer
18 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 ...
1
vote
0answers
12 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
23 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: ...
1
vote
0answers
45 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
13 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
0answers
15 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 | ...
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
24 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
52 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
17 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 ...
0
votes
1answer
26 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
34 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 | ...
7
votes
1answer
131 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 ...
2
votes
1answer
40 views

Converting to Chomsky Normal form- derivations

I'm attempting to convert the following grammar into Chomsky Normal Form: $$S \to a S b S \mid b S a S \mid ε$$ I'm confused because in every example I've seen the grammar has been broken up into ...
0
votes
0answers
25 views

Construct Context free grammar for

Construct Context free grammar for Language $L=\{a,b\}^*-\{a^nb^n|n\geq 0\}$ i am not able to approach to how to consider all cases
0
votes
0answers
35 views

Construct the Context Free Grammar

Construct the Context Free Grammar that generates the language $L=\{W\in \{a,b\}^*| W\text{contains more a's than b's} \}$ $S\mapsto AaA$ $A\mapsto \epsilon |aA|Aa|aAb|bAa|AA$ Is this answer is ...
1
vote
1answer
69 views

disprove $L = \{ a^nb^n\mid n \geq 0 \}$ is not a context-free using pumping lemma for CFL

I am writing something about pumping Lemma. I know that the language $L = \{ a^nb^n\mid n \geq 0 \}$ is context-free. But I don't understand how this language satisfies the conditions of pumping lemma ...
-2
votes
1answer
37 views

CFG with reverse strings

I've been trying to figure this out for a while, and I'm at a total loss: Write a context-free grammar that generates the language $\{x y\ |\ x$ is a string over $\{a,b,c\},\ y$ is a reverse of ...
0
votes
1answer
38 views

Find CFG for language

I'm trying to find CFG of language where $L = \{ a^x b^y a^z \}$ where x,y,z = 1 2 3.. .and y = 2x + 2z I have no idea, I'm completely stuck. Any help would be very appreciated thank you
0
votes
1answer
19 views

Given the following grammars with start symbol $\langle S \rangle$, specify the type ($0$, $1$, $2$ or $3$)

So I'm working on this problem set and I'm having some trouble figuring out what type each one of these are. I think (a) is type $0$ and really can't tell for (b). I know the difference between each ...
4
votes
1answer
80 views

Turing Machine Problem

We know, A Turing machine is a hypothetical device that manipulates symbols on a strip of tape according to a table of rules I Draw a TM for input $x=(0+1)^*$ i want to implement ...
5
votes
1answer
28 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
56 views

PDA and Some language Grammar inference

L1={$w^* $| w=x and $ x \in \Sigma^*$} L2={$ww^R ww^R $| $ w \in ( \Sigma + \Sigma)^*$} L3={$w | w=xy, x,y \in \Sigma^*$, y is a substring of x} a) there is a PDA(push down automata) that accept ...
1
vote
1answer
21 views

Context Free Grammar for substrings of similar length [closed]

am unable to find a CFG for the following. I would really appreciate some help as im stuck for 2 days now: $$ L=\{a^nb^ma^rb^s : n+m = r+s\} $$ Thanks a million!!!
3
votes
1answer
45 views

A CFG Grammar for One Language

Suppose : $w_1,w_2 \in \{a,b\}^∗$ and $ L=\{w_1w_2 \mid w_1,w_2 \in \{a,b\}^* \land n_a(w_1)=n_b(w_2)\}$ $n_a$ is number of $a$'s and $n_b$ is number of $b$'s. This is a Entrance Exam question. I ...
2
votes
1answer
65 views

Challenge on Property of Complement in Language

We have: and M be a finite automata. Suppose d(M) be a deterministic automata that equivalence to M. if $M_1$ and $M_2$ be two finite automata, $M_1 + M_2$ is the finite automata such that the ...
1
vote
0answers
36 views

Language of Specific Grammar

I ran into this exercise in Sipser's Note on Computation Theory. Consider the following grammar $G$: $$\begin{align} S &\to aSD \;|\; bB \\ D &\to dS \;|\; a \\ B &\to bB \;|\; ...
0
votes
1answer
19 views

Can two different rules be applied at the same step in Type 0 Grammar

As a rule in CFG, we have the liberty of applying any rule for the string S anywhere in the derivation. We can also apply different rule in one step. For example, consider the string S->0S1S and say ...
0
votes
1answer
25 views

CFG for $a^ib^jc^k | i\neq j\ or\ j\neq k$

This is my Homework problem. Can someone please help me out! Find CFG(Context Free Grammar) for the language L={$a^ib^jc^k | i\neq j\ or\ j\neq k$}.
0
votes
1answer
21 views

Algorithm that takes input desc. of two PDAs and outputs intersection of langs. recognized by two PDAs

Does there exist an algorithm which takes as input the descriptions of two pushdown automata, $P1$ and $P2$, and prints the description of another pushdown automaton which recognizes the intersection ...
0
votes
0answers
30 views

Find an unambiguous grammar for this

S → aS | aSbS | (empty) where the alphabet is $\{a,b\}$ in other words, the set of strings where any prefix has at least as many 'a's as 'b's.
0
votes
1answer
31 views

How does the push-down automaton have to look like?

Could you give me a hint how to find a push-down automaton for the language: $$L=\{ a^n b^{2n} | n \in \mathbb{N}\}$$ How does the push-down automaton have to look like?
0
votes
1answer
25 views

Context free grammar and pumping lemma

I have a language $ L = { (b_i \# b_{i+1} ) } $ where $ b_i \ge 1 $ and $ b_i $ is binary representation of number $ i \ge 1 $ I have a word $ w = 10^N1^N1 \# 10^{N-1}10^N0$ and $ w = uvxyz $ Could ...
0
votes
0answers
19 views

Language generated by grammar

I have difficulty in finding the language generated by this grammar $ S -> \epsilon | a | EaRB $ $R -> K | KDR $ $aK -> KaA $ $ Aa -> aA $ $ AD -> Da $ $ AB -> Ba $ $Eka -> ...
1
vote
1answer
29 views

Chomsky normal form complexity

How to prove that the complexity of transforming any context-free grammar without epsilon productions to chomsky normal form is $ O(N^2) $ , because I found this in 2 articles, but without proof
1
vote
1answer
41 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
1answer
54 views

help to fine about CFG for $L=\{a^nb^mc^k:|n-m|=k\}$

Hi guys (and so sorry for my weak english). I have a problem about this language: $$L=\{a^nb^mc^k:|n-m|=k\}.$$ This language wants to produce some $k$ with $|n-m|$ but about another kind of this ...
0
votes
1answer
24 views

w such that contains at most two 1s, CFG idea

this is my first time that I did a CFG and I ask if it's correct or not. My idea is the follow: A -> 0A | 1B B -> 0B | 1C C -> 0C As the CFG has to ...
1
vote
1answer
96 views

Context free grammar $L=\{a^ib^jc^k|j=i+k-2\}$

$L=\{a^ib^jc^k|j=i+k-2\}$ This expression surprise me a lot and put me into deep thinking. what i am doing by solving the expressions: ...
1
vote
1answer
51 views

Deterministic Push-Down Automata

Does there exist Deterministic Push-Down Automata for the language below. Any kind of answer will be highly appreciated! $$L =ba^nb^n U bba^nb^{2n}$$
1
vote
2answers
62 views

Can an infinite set of primes be a regular language or CFG?

At first glance, it seems like the pumping lemmas should somehow "easily" show that an infinite set of primes (say, written in binary) cannot be a regular language or context-free grammar. But I don't ...
2
votes
0answers
16 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 ...