need help with q20 ? e Tanguage L,U L2 is nonregular. that Lt L2 is nonregular l
ID: 3738279 • Letter: N
Question
need help with q20 ?
e Tanguage L,U L2 is nonregular. that Lt L2 is nonregular lusions of parts (a) and (b) are not true if L2 is not assumed to of languages Lj and Ly over ta. b) tht satisty the following descrip L2 is nonregular, and L' U L2 is regular. Ly is regular, is y L is regular, L2 is c) Lt is regular, is lar. Lgular. L is nonregular, and Lj UL is nonregular ar. Lz is nonregular, and LinL is regular. lar, L2 is nonregular, and Lj UL2 is regular is nonregular and L? is regular. e, Li nd ?2 be two alphabets. A string homomorphism is a total function h from ??; that preserves concatenation. That is, h satisfies (uv)h(u)h(v). C2; be a regular language. Show that the set (h(w) w EL) is regular over This set is called the homomorphic image of L, under h. be the E2. L2 c ?; be a regular language. Show that the set {w E ?|h(w) e L2} is b) Let regular. This set is called the inverse image of L2 under h tontext- free grammar G = (V, ?, P, S) is called right-linear if each rule is of the form i) A?u, or mple where A, B e V, and u ? ?*. Use the techniques from Section 6.3 to show that the right-linear grammars generate precisely the regular sets. 21. A context-free grammar G-(V, ? , P, S) is called left-regular if each rule is of the form ii) A?a, or EV,and a ? ?.Explanation / Answer
Solution:
The grammar will be considered to be generating regular sets when it is either left recursive or right recursive but not both.
The given grammar is a right linear grammar, this means that the parsing from this grammar will be unique for every input string
this means that the given grammar will generate the regular sets and will also be generated using finite automata.
This kind of grammar is also considered to be unambiguous grammar.
For example:
i)
A=> u
A=> uB
The sets generated from the grammar will be growing in one direction which is right-hand side, so we can conclude that the set generated will be a regular set.
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.