The tag has no wiki summary.

learn more… | top users | synonyms (1)

1
vote
1answer
33 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
14 views

Context Free Grammar for substrings of similar length [on hold]

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
36 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
59 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
27 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
15 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
16 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 ...
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.
1
vote
1answer
25 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
23 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
16 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
1
vote
1answer
36 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
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 ...
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
50 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
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}$$
1
vote
2answers
32 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
30 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
23 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
30 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
38 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
32 views

Chomsky Normal Form for Integer Recognition

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

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
30 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
17 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
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
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 ...
-1
votes
2answers
81 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
32 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
29 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
21 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
18 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
27 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.
0
votes
1answer
30 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 ...
2
votes
1answer
50 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 ...
0
votes
1answer
10 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
50 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 ...
1
vote
1answer
34 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
92 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... ...