The tag has no wiki summary.

learn more… | top users | synonyms (1)

0
votes
1answer
12 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
13 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 ...
1
vote
1answer
528 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, ...
2
votes
1answer
59 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 ...
0
votes
1answer
39 views

Basic Question about ambiguity of Grammar

I saw one book in Computation Course. I take a picture from this book, and in this book say why (or not) the following grammar is ambiguous? I couldn't find any solution to prove it's ambiguous. ...
3
votes
1answer
19 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
38 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
15 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!!!
2
votes
1answer
40 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
60 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
32 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
17 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
18 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
15 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 ...
1
vote
1answer
32 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$$ ...
2
votes
1answer
119 views

Converting Context Free Grammar to Chomsky Normal Form

This is an exercise that I had to complete in my class and I struggled a lot with it $$\begin{align*} &S\to 0A0\mid 1B1\mid BB\\ &A\to C\\ &B\to S\mid A\\ &C\to S\mid\epsilon ...
0
votes
0answers
26 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
27 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
20 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
0
votes
2answers
228 views

Construct context-free grammar for $\{a^ib^jc^k : i\le j+k\}$

I'm looking through several of old exam sets in order to prepare for the exam and now I'm stuck on this exercise, where we have to construct a context-free grammar for the language: $$L = ...
3
votes
1answer
4k views

Converting to Chomsky Normal Form

I am trying to learn how to convert any context free grammar to Chomsky Normal Form. In the example below, I tried to apply Chomsky Normal Form logic, to result in a grammar, where every symbol either ...
1
vote
1answer
38 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
25 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
28 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
0
votes
1answer
22 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
36 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}$$
0
votes
1answer
46 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 ...
1
vote
1answer
55 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
2answers
197 views

Is my example enough for the question below, CFG, Please Help

Is my example enough for the question below: $Question:$ Give a counterexample to show that the following construction fails to prove that the class of context-free languages is closed under star. ...
0
votes
2answers
123 views

Prove a CFG is ambiguous

I need to prove this context free grammar ambiguous, I know to prove this I need to find 2 different paths of the same string, but this question has 'begin' and 'end' which I don't know what they mean ...
0
votes
1answer
33 views

Chomsky Normal Form for Integer Recognition

If I have the following CFG, which is just the regex [0-9]+: ...
0
votes
3answers
100 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 ...
1
vote
2answers
36 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 ...
0
votes
0answers
25 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
16 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
31 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
39 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
0answers
25 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 = ...
1
vote
1answer
23 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
0answers
31 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
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 ...
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
31 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
18 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
35 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
25 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 ...