The tag has no wiki summary.

learn more… | top users | synonyms (1)

1
vote
0answers
5 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
24 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
33 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
14 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
20 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
27 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
127 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
35 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
18 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
34 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
62 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 ...
-1
votes
0answers
12 views

Context-Free Grammar

I am trying to create a context-free grammar for the alphabet over a,b which will account for "at most 2 b's" My attempt is here: S -> bSb | bSb| epsilon
-2
votes
1answer
30 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
30 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
73 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 ...
4
votes
1answer
25 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
51 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
20 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
43 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
62 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
33 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
18 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
22 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
20 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
27 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
24 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
18 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
24 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
39 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
51 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
23 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
82 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
45 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
51 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
15 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
35 views

Checking my CFG to CNF answer

I attempted to transform the given CFG into CNF. $$S → ASA|A$$ $$A→aa|ε$$ Here are my steps: $$S→X$$ $$X→XA|AX|A$$ $$A→aa$$ $$S→X$$ $$X→XA|AX|YY$$ $$A→YY$$ $$Y→a$$ $$S→XA|AX|YY$$ ...
0
votes
0answers
28 views

CFG Convertion to GNF

I have a very simple CFG that I am trying to convert into GNF. The CFG is: S -> aSbS S -> epsilon I looked at the CFG and I think I can just do the ...
2
votes
0answers
17 views

Are there general guidelines to make a grammar unambiguous?

I realized that we can't have more than one uppercase letter of the same type. For instance, we can have S -> AB, but not S -> BB. Is there any other principles we must abide to when writing an ...
1
vote
1answer
33 views

How come this grammar is unambiguous?

Equivalent unambiguous grammar: \begin{align} S &\rightarrow ABA|AB|BA|A|B \\ A &\rightarrow aA | a \\ B &\rightarrow aB|b \end{align} an unambiguous language has only one parse ...
0
votes
0answers
43 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
24 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
1answer
34 views

Chomsky Normal Form for Integer Recognition

If I have the following CFG, which is just the regex [0-9]+: ...
0
votes
0answers
27 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
1answer
29 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
24 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
34 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
1answer
26 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
33 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 ...