1. Let = {1, o} . Consider the following three languages a) [lol n 2 0] For each
ID: 3871163 • Letter: 1
Question
1. Let = {1, o} . Consider the following three languages a) [lol n 2 0] For each, show if the given language is regular or not. For nonregular languages, try to give a CFG or a PDA, either of which would imply that the given language is still context free 2. It is known that . [an |n 2 0 is regular as it can be recognized by a FA anbn | n > 0} is context free as it can be recognized by a PDA (anbncn | n > 0} is not context free as it cannot be recognized by a PDA · FA was generalized by adding one stack, yielding the PDAs. PDAs in turn can be generalized by adding more stacks. Suppose we have two stacks, so that the transitions in the state diagram are indicated with a, b, (cl , C2) d, (el, e2), where a, d E Q denote the current and next state, b is the input symbol read, (c1,c2) denote the symbols at the top of the stack 1 and 2, respectively, and (e1, e2) are symbols pushed back to the corresponding stacks. As before, any of the (b, c1, c2, e1,e2) can be e indicating that the corre sponding parameter/operation is omitted. Draw a state diagram for two-stack PDA that recognizes 3. If A and B are languages, define A. B = {xy | x E A and y E B and 1x1 = 1y13-Show that if A and B are regular languages, then AB is a CFL. 4. Let (0, 1} and let B be the collection of strings that contain at least one 1 in their second half, i.e., B = {uulu E *, u E *, and lul > 1 a) Give a PDA that recognizes B b) Give a CFG that generates BExplanation / Answer
1) a) L={lol,n>=0}. It is a Regular Language and can be made with 5 states.3 States to remeber, 1 for initial state and 1 for the trap state.
b)L={lnoln,n>=0}. This is a context free language and can be done by PDA and not FA .It requires push and pop. n l's are pushed on to the stack and the next o is ignored and then the remaining l's are used to pop out the previously inserted l's.
c) L={lonl,n>=0}. It is a Regular Language as on does not require any comparision, and it can be self looped.
d) L={(lol)n,n>=0}. It is a Regular Language as the whole string lol can be self looped.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.