2) Write a CFG for L = {w | w has an equal number of a's...

Question

Question

2) Write a CFG for L = {w | w has an equal number of a's and b's } over the alphabet {a,b,c}.

Answer 1

Answer #1

Grammar:
-----------
S -> aB | bA | cS | 
A -> aS | bAA | cA
B -> bS | aBB | cB

Answer 2

Similar Homework Help Questions

I have below questions with answer! what if we get different question: Write a CFG without...

I have below questions with answer! what if we get different question: Write a CFG without empty rules that generates the language: L = strings from (a ∪ b)*c* where the number of a's and b's together is equal to the number of c's. Answer: S → Asc | ε A → a | b ================================================== Write a CFG without empty rules that generates the language: L = strings from (ab ∪ cb)*c* where the number of a's and b's...
Theory of Computation - Push Down Automata (PDA) and Context Free Grammars (CFG) Problem 1. From...

Theory of Computation - Push Down Automata (PDA) and Context Free Grammars (CFG) Problem 1. From a language description to a PDA Show state diagrams of PDAs for the following languages: a. The set of strings over the alphabet fa, b) with twice as many a's as b's. Hint: in class, we showed a PDA when the number of as is the same as the number of bs, based on the idea of a counter. + Can we use a...
Consider the language L _ {w E {a,b)' : the longest run of a's in u,...

Consider the language L _ {w E {a,b)' : the longest run of a's in u, is longer than any run of b's in w} For example, abbbbaabbbaaaaa E L because the longest run of b's in it has length four, while the longest run of a's has length six. Prove that L is not context-free.

Design a CFG (Context Free Grammar) for each of the following languages: L4 = {w |...

Design a CFG (Context Free Grammar) for each of the following languages: L4 = {w | w does not have exactly as many a's as b's}.
Give a Context Free Grammar (CFG) for the following language: L = { w | the...

Give a Context Free Grammar (CFG) for the following language: L = { w | the number of a’s and the number of b’s in w are equal, ∑= {a, b} }
1) Assume ∑ = {a, b}, construct a DFA to recognize: {w | number of a's...

1) Assume ∑ = {a, b}, construct a DFA to recognize: {w | number of a's in w ≥ 2 and number of b's in w ≤ 1}. (seven states) 2) Assume ∑ = {a, b}, construct a DFA to recognize: {w || w | ≥ 2, second to the last symbol of w is b}. (four states) 3) Write a regular expression for: All bit strings that contain at least three 1's.

1. Construct a DFSM to accept the language: L = {w € {a,b}*: w contains at...

1. Construct a DFSM to accept the language: L = {w € {a,b}*: w contains at least 3 a's and no more than 3 b's} 2. Let acgt} and let L be the language of strings consisting of repeated copies of the pairs at, ta, cg, gc. Construct both a DFSM to accept the language and a regular expression that represents the language 3. Let a,b. For a string w E ', let W denote the string w with the...
Input alphabet {a,b 1. write the CFG for the language of palindromes (5 points) 2. Convert this i...

Input alphabet {a,b 1. write the CFG for the language of palindromes (5 points) 2. Convert this into PDA (state the accepting condition) (10 points) . Write a PDA for this language that satisfies the conditions required to convert it into CFG (5 points) 4. Convert the PDA from Q3 into CFG (10 points) Input alphabet {a,b 1. write the CFG for the language of palindromes (5 points) 2. Convert this into PDA (state the accepting condition) (10 points) ....
Consider the given CFG: S ⟶ a X a X a , X ⟶ a X...

Consider the given CFG: S ⟶ a X a X a , X ⟶ a X | b X | Λ What is the language this CFG generates? a) a language with all strings of at least 3 a's b) a language with all strings of a's and b's c) a language with all strings that start and end with a's with at most 3 a's d) a language with all strings of at most 3 a's e) None of...

8 Find CFGs that for these regular languages over the alphabet a, b. Draw a Finite...

8 Find CFGs that for these regular languages over the alphabet a, b. Draw a Finite Automata first and use this to create the CFG (a) The language of all words that consist only of double letters (aa or bb) (b) The set of all words that begin with the letter b and contains an odd number of a's or begin with the letter a and contains an even number of b's.