Let = {0,1}. Let C 1 be the language of all strings that contain a 1
Question:
Let Σ = {0,1}. Let C1 be the language of all strings that contain a 1 in their middle third. Let C2 be the language of all strings that contain two 1s in their middle third. So C1 = {xyz| x, z ∈ Σ* and y ∈ Σ*1Σ*, where |x| = |z| ≥ |y|} and C2 = {xyz| x, z ∈ Σ* and y ∈ Σ*1Σ*1Σ*, where |x| = |z| ≥ |y|}.
a. Show that C1 is a CFL.
b. Show that C2 is not a CFL.
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Answer rating: 75% (8 reviews)
a To show that C1 is a contextfree language CFL we can use the pumping lemma for contextfree languag...View the full answer
Answered By
Mubarak Ali
I am serving as a Computer Science lecturer at different Colleges for more then 5 years. I delivered lectures to different Class Like:-
1:- Intermediate
2:-BS-Program(Subject)
3:-B.Sc
4:-Master Classes.
My teaching method is to simple that's way students get information in the easy way
0.00
0 Reviews
10+ Question Solved
Related Book For
Question Posted:
Students also viewed these Computer science questions
-
Let F be the language of all strings over {0,1} that do not contain a pair of 1s that are separated by an odd number of symbols. Give the state diagram of a DFA with five states that recognizes F....
-
Let B be the language of all palindromes over {0,1} containing equal numbers of 0s and 1s. Show that B is not context free.
-
In certain programming languages, comments appear between delimiters such as /# and #/. Let C be the language of all valid delimited comment strings. A member of C must begin with /# and end with #/...
-
You are an information technology (IT) intern working for Health Network, Inc. (Health Network), a fictitious health services organization headquartered in Minneapolis, Minnesota. Health Network has...
-
Solve Problem x/-4 < 5/6
-
Post-Test Management Science True or False (Please place your answer to the left of the number) 1. Decision making and problem solving both involve quantitative methods, but one really has nothing...
-
Explain the importance of incident reporting, sentinel events, and the purpose of root cause analyses.
-
Maine Department Store is located near the Village Shopping Mall. At the end of the companys calendar year on December 31, 2010, the following accounts appeared in two of its trial balances....
-
(A) We are given three diffent vectors: A = 6-3, B=-11+5j and C = A + B. (1) C = 2, (2) C = 51, (3) C = 5 + 2), (4) C=7+8 What is C in component form? A. 3 B. 1 C. 4 D. 2 Using the same three vectors...
-
The trial balance of Biju Medical Supplies at the end of its fiscal year, August 31, 2020, includes these accounts (amounts in thousands): Inventory Rp17,200; Purchases Rp149,000; Sales Revenue...
-
Let = {0,1} and let B be the collection of strings that contain at least one 1 in their second half. In other words, B = {uv| u * , v * 1 * and |u| |v|}. a. Give a PDA that recognizes B. b....
-
We defined the rotational closure of language A to be RC(A) = {yx| xy A}. Show that the class of CFLs is closed under rotational closure.
-
The probability that a certain door is locked is 0.6. The key to the door is one of five unidentified keys hanging on a key rack. You randomly select two keys before approaching the door. What is the...
-
Suppose you are given two urns, numbered Urn I and Urn II. Contents of Urn I: 5 red, 6 blue, and 10 green marbles Contents of Urn II: 30 red, 20 blue, and 10 green marbles The probability of...
-
A client has had an unanticipated event which has depleted his emergency reserves. He needs an additional $10,000 and has to sell one of his municipal bonds. The following bonds have similar ratings...
-
Which is an advantage to an employee who participates in a profit-sharing plan? A. Employee does not have to make investment decisions. B. Graded vesting schedule. C. Older employees receive the...
-
Which of the following is true about cash balance plans? I. Past service credit is available. II. Employer guarantees a minimum rate of return. III. Participants direct investments in hypothetical...
-
Which type of funding vehicle is not approved for 403(b) plans? A. Mutual fund. B. Variable annuity contract. C. Individual securities. D. Fixed annuity contract.
-
Molson-Coors Brewing Company (TAP) reported the following operating information for a recent year (in millions): Sales ................................................ $3,568 Cost of goods sold...
-
a. Why does the Wi-Fi Alliance release compatibility testing profiles in waves instead of combining the entire standards features initially? 27a1.) An 802.11ac Wi-Fi compatibility testing profile...
-
Suppose you have a deque D containing the numbers (1,2,3,4,5,6,7,8), in this order. Suppose further that you have an initially empty queue Q. Give a code fragment that uses only D and Q (and no other...
-
What values are returned during the following sequence of deque ADT operations, on an initially empty deque? addFirst(3), addLast(8), addLast(9), addFirst(1), last( ), isEmpty( ), addFirst(2),...
-
Had the queue of the previous problembeen an instance of the ArrayQueue class, from Code Fragment 6.10, with capacity 30 never exceeded, what would be the final value of the instance variable f?
-
A friend owes you $500 in 1 year from now, and then $1000 2 years from now. Both loans are at 5%. If you want to replace both of these loans with ONE PAYMENT NOW, how much would your friend give you ?
-
If the amount of retained earnings at the beginning of the year was $ 3 0 , 0 0 0 , and $ 1 2 , 0 0 0 in dividends is paid during the year, calculate net income for the year.
-
On January 2, 20Y4, Whitworth Company acquired 33% of the outstanding stock of Aloof Company for $330,000. For the year ended December 31, 20Y4, Aloof Company earned income of $86,000 and paid...
Study smarter with the SolutionInn App