Prova1_ftc

continuacao 2 AFD -> GR + 1 = b + 0 = a + ABC = E + AC = F G = ( {A,C,D,E,F}, {a,b}, P, A ) P: A -> aE | bD | λ C -> bD D -> aC | bD | λ E -> aE | bE | λ F -> aE | bD | λ 3) 1^n 0^m n = m 1^m 0^n n > m 1^m 0^m 1^n n < m L = { 1^n 0^m 1^n | 1^m < n } Suponha que L' é uma gramatica regular. Por uma au algumamento, então existe um automato finito para L'. Como w = 1^0 0^1 uma entrada em L, temos que w \in L e L = { 1^ri } para n >= 0 |uv^i e L para todo i>= 0 A |uv| < k e |v| > 0, convanendo que Z' = |xv| com uma soma em x e xy| <= k. |w = uvx |m|e uv = z. L | uv^0 | < K +1 L | uv | < 0 ..u v e \in L para todo i > 0 (convencao de |eacional.) 4.) L = { 1^m 0^n 1^m | m = n } GLC L2 = ( {P}, {a,b}, P ) P -> a a P b | a b | λ 4-B conti. b: a + c a: par c: impar P -> ABC A -> aa A b | λ B -> bb B | λ C -> c | 1B | λ AP para L2 : -> *\lambda A B C * A 1A a A b b | 1B * B 1B b B | λ * C 1C c | 1B | λ * a | λ a 1 a 2x b b 1 a 2 c 1 c 2x GLL L2 : ( {P},{a,b,c}, TR1, {P} ) Onde: R: P -> ABC A -> aa A bb | 1B B -> bb | 1B | λ C -> c | 1B | λ