![Problem 1 Create a CFG that generates each of the languages below. [10 points] [10 points] wR is a substring of r if there are strings y, z E {a, b) such that r = ywR2. A = {w I w E {a, b) has more as than bs} B = {w#r l w,xe(a, b) and wR a. b. is a substring of r). Rememb er, c. [10 points] C = {ambck 1 m, n > 0 and k = m + n).](http://img.homeworklib.com/questions/d3321a20-65fb-11eb-9508-dd66325f6b18.png?x-oss-process=image/resize,w_560)
Homework Answers
Below are the CFG's as per the languages specified by you:
Solution a.
S -> Ta | RS | SRT
T -> Ta | λ
R -> RR | aRb | bRa | λ
Solution b.
S → T R
T → aTa | bTb | #R
R → RR | a | b
Solution c.
S → aSc | B
B → bBc | λ
I hope I could solve your problem.Further, if you have any doubt, please ask.
Add Answer to:
Problem 1 Create a CFG that generates each of the languages below. [10 points] [10 points]...
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...
Question 8 10 pts Let S = {a,b,c}. Write a grammar that generates the language: L...
Question 8 10 pts Let S = {a,b,c}. Write a grammar that generates the language: L = {(ac)"6n+1w: n > 0, W € 2*, W contains the substring acb}
Let L, be the language accepted by the DFA below and L2 = {0"1"Om1 mol 1|n,...
Let L, be the language accepted by the DFA below and L2 = {0"1"Om1 mol 1|n, m, k > 0}. Create a CFG that generates L3 = L, UL2 using the techniques pre sented in textbook. 0 start -> 0 10
Give a context free grammar for the language L where L = {a"bam I n>:O and...
Give a context free grammar for the language L where L = {a"bam I n>:O and there exists k>-o such that m=2"k+n) 3. Give a nondeterministic pushdown automata that recognizes the set of strings in L from question 3 above. Acceptance should be by accept state. 4. 5 Give a context-free grammar for the set (abc il j or j -k) ie, the set of strings of a's followed by b's followed by c's, such that there are either a...
1. Give a context-free grammar for the set BAL of balanced strings of delimiters of three...
1. Give a context-free grammar for the set BAL of balanced strings of delimiters of three types (), and . For example, (OOis in BAL but [) is not. Give a nondeterministic pushdown automata that recognizes the set of strings in BAL as defined in problem 1 above. Acceptance should be by accept state. 2. Give a context free grammar for the language L where L-(a"b'am I n>-o and there exists k>-o such that m-2*ktn) 3. Give a nondeterministic pushdown...
Problem 1. (10 points) For each of the following statements determine whether it is true or...
Problem 1. (10 points) For each of the following statements determine whether it is true or false. * (+1 for correct, 0 for blank, -0.5 for incorrect) The grammar SaSb generates {w € {a,b}" : #a = #b}. T F A CFG is ambiguous if there is exactly one parse tree for every word. TF Two different CFGs could generate two different languages. T F An NPDA could have no final states and still accept the word abba. T F...
disprove that the given lan 4. [20 Points For each of the following languages, prove or guage is regular (a) L1www e {a...
disprove that the given lan 4. [20 Points For each of the following languages, prove or guage is regular (a) L1www e {a,b}*} {w w E {a, b}* and no two b's in w have odd number of a's in between}. (b) L2 (c) L3 a" (d) L4 vw n = 3k, for k > 0}. a, b}*}
disprove that the given lan 4. [20 Points For each of the following languages, prove or guage is regular (a) L1www e...
Construct context-free grammars that generate each of these languages: A. tw E 10, 1 l w...
Construct context-free grammars that generate each of these languages: A. tw E 10, 1 l w contains at least three 1s B. Hw E 10, 1 the length of w is odd and the middle symbol is 0 C. f0, 1 L fx l x xR (x is not a palindrome) m n. F. w E ta, b)* w has twice as many b's as a s G. a b ch 1, J, k20, and 1 or i k
2. (10 points) Determine whether the following languages are decidable, recognizable, or undecidable. Briefly justify y...
2. (10 points) Determine whether the following languages are decidable, recognizable, or undecidable. Briefly justify your answer for each statement. 1) L! = {< D,w >. D is a DFA and w E L(D)} 2) L2- N, w> N is a NF A and w L(N) 3) L,-{< P, w >: P is a PDA and w ㅌ L(P); 4) L,-{< M, w >: M is a TM and w e L(M)} 5) L,-{< M, w >: M is a...
Question 3 Give a context-free grammar for each of the following languages over = {a,b,c}. 1....
Question 3 Give a context-free grammar for each of the following languages over = {a,b,c}. 1. {a^jen: n >0}. 2. {animck : k=n+m} 3. Strings of a's and b's that contain twice as many a's as b's (for example, aba).
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...
Question 8 10 pts Let S = {a,b,c}. Write a grammar that generates the language: L = {(ac)"6n+1w: n > 0, W € 2*, W contains the substring acb}
Let L, be the language accepted by the DFA below and L2 = {0"1"Om1 mol 1|n, m, k > 0}. Create a CFG that generates L3 = L, UL2 using the techniques pre sented in textbook. 0 start -> 0 10
Give a context free grammar for the language L where L = {a"bam I n>:O and there exists k>-o such that m=2"k+n) 3. Give a nondeterministic pushdown automata that recognizes the set of strings in L from question 3 above. Acceptance should be by accept state. 4. 5 Give a context-free grammar for the set (abc il j or j -k) ie, the set of strings of a's followed by b's followed by c's, such that there are either a...
1. Give a context-free grammar for the set BAL of balanced strings of delimiters of three types (), and . For example, (OOis in BAL but [) is not. Give a nondeterministic pushdown automata that recognizes the set of strings in BAL as defined in problem 1 above. Acceptance should be by accept state. 2. Give a context free grammar for the language L where L-(a"b'am I n>-o and there exists k>-o such that m-2*ktn) 3. Give a nondeterministic pushdown...
Problem 1. (10 points) For each of the following statements determine whether it is true or false. * (+1 for correct, 0 for blank, -0.5 for incorrect) The grammar SaSb generates {w € {a,b}" : #a = #b}. T F A CFG is ambiguous if there is exactly one parse tree for every word. TF Two different CFGs could generate two different languages. T F An NPDA could have no final states and still accept the word abba. T F...
disprove that the given lan 4. [20 Points For each of the following languages, prove or guage is regular (a) L1www e {a,b}*} {w w E {a, b}* and no two b's in w have odd number of a's in between}. (b) L2 (c) L3 a" (d) L4 vw n = 3k, for k > 0}. a, b}*}
disprove that the given lan 4. [20 Points For each of the following languages, prove or guage is regular (a) L1www e...
Construct context-free grammars that generate each of these languages: A. tw E 10, 1 l w contains at least three 1s B. Hw E 10, 1 the length of w is odd and the middle symbol is 0 C. f0, 1 L fx l x xR (x is not a palindrome) m n. F. w E ta, b)* w has twice as many b's as a s G. a b ch 1, J, k20, and 1 or i k
2. (10 points) Determine whether the following languages are decidable, recognizable, or undecidable. Briefly justify your answer for each statement. 1) L! = {< D,w >. D is a DFA and w E L(D)} 2) L2- N, w> N is a NF A and w L(N) 3) L,-{< P, w >: P is a PDA and w ㅌ L(P); 4) L,-{< M, w >: M is a TM and w e L(M)} 5) L,-{< M, w >: M is a...
Question 3 Give a context-free grammar for each of the following languages over = {a,b,c}. 1. {a^jen: n >0}. 2. {animck : k=n+m} 3. Strings of a's and b's that contain twice as many a's as b's (for example, aba).
Most questions answered within 3 hours.
-
Brian makes $34,100 per year. How much can Brian expect to
contribute to FICA taxes in...
asked 14 minutes ago -
To buy a new house you must borrow $155,000. To do this you take
out a...
asked 29 minutes ago -
Spacely Sprockets is evaluating the construction of a new plant
on land the company purchased for...
asked 1 hour ago -
1. Consider a linear regression model of y on K regressors and
an intercept.
(i) Describe...
asked 1 hour ago -
Enter a balanced equation for the reaction between hydrochloric
acid and sodium sulfite.
Express your answer...
asked 1 hour ago -
Give a regular expression describing the language
{x | x ∈ Σ* and x does not...
asked 1 hour ago -
Masses of 1.0 kg, 2.0 kg, and 3.0 kg are each separately subject
to a net...
asked 1 hour ago -
The mode of philosophical argumentation and thought. How do
philosophers think and write? What is important...
asked 1 hour ago -
At the beginning of the unit, you were asked whether you thought
it was appropriate or...
asked 1 hour ago -
Calculate the grams of carbon in 9.32 x 10+23 molecules of
benzene (C6H6).
asked 1 hour ago -
A 5-year Treasury bond has a 4.95% yield. A 10-year Treasury
bond yields 6.6%, and a...
asked 1 hour ago -
suppose you own a chain of five restaurants in
downtown Vancouver. as the manager, you want...
asked 2 hours ago