Lista de Exercicios sobre Forma Normal de Chomsky e Greibach

APS Professor Sérgio Assunção Monteiro email smonteirounicariocaedubr 1 A atividade deve ser entregue individualmente no local apropriado do AVA 2 As resoluções da atividade devem ser entregues no formato PDF 3 A atividade deve conter 1 Nome da disciplina 2 Código da Turma 3 Nome e matrícula do aluno 4 A data de entrega é até 05MAIO2021 5 Todas as respostas devem ser detalhadas e apresentar os resultados Questão Considere a GLC abaixo S AY XX A X b SX ε Y p A w Y Agora faça a Obtenha a respectiva forma Normal de Chomsky b Obtenha a respectiva forma Normal de Greibach a 𝑆0 𝑆 𝑆 𝐴𝑌 𝑋𝑋 𝐴 𝑋 𝑏 𝑆𝑋 ε 𝑌 𝑝 𝐴 𝑤 𝑌 Resolver problema 𝑋 ε 𝑆0 𝑆 𝑆 𝐴𝑌 𝑋𝑋 𝑋 𝐴 ε 𝑋 𝑏 𝑆𝑋 𝑆 𝑌 𝑝 𝐴 𝑤 𝑌 Resolver problema 𝑆 ε 𝑆0 𝑆 ε 𝑆 𝐴𝑌 𝑋𝑋 𝑋 𝐴 𝑋 𝑏 𝑆𝑋 𝑆 𝑌 𝑝 𝐴 𝑤 𝑌 Resolver problema 𝐴 𝑌 𝑆0 𝑆 ε 𝑆 𝐴𝑌 𝑋𝑋 𝑋 𝐴 𝑋 𝑏 𝑆𝑋 𝑆 𝑌 𝑝 𝐴 𝑤 𝑝 Resolver problema 𝑋 𝑆 𝑆0 𝑆 ε 𝑆 𝐴𝑌 𝑋𝑋 𝑋 𝐴 𝑋 𝑏 𝑆𝑋 𝐴𝑌 𝑋𝑋 𝐴 𝑌 𝑝 𝐴 𝑤 𝑝 Resolver problema 𝑋 𝐴 𝑆0 𝑆 ε 𝑆 𝐴𝑌 𝑋𝑋 𝑋 𝐴 𝑋 𝑏 𝑆𝑋 𝐴𝑌 𝑋𝑋 𝑤 𝑝 𝑌 𝑝 𝐴 𝑤 𝑝 Resolver problema 𝑆 𝐴 𝑆0 𝑆 ε 𝑆 𝐴𝑌 𝑋𝑋 𝑋 𝑤 𝑝 𝑋 𝑏 𝑆𝑋 𝐴𝑌 𝑋𝑋 𝑤 𝑝 𝑌 𝑝 𝐴 𝑤 𝑝 Resolver problema 𝑆 𝑋 𝑆0 𝑆 ε 𝑆 𝑏 𝑆𝑋 𝐴𝑌 𝑋𝑋 𝑤 𝑝 𝑋 𝑏 𝑆𝑋 𝐴𝑌 𝑋𝑋 𝑤 𝑝 𝑌 𝑝 𝐴 𝑤 𝑝 Resolver problema 𝑆0 𝑆 𝑆0 𝑏 𝑆𝑋 𝐴𝑌 𝑋𝑋 𝑤 𝑝 ε 𝑆 𝑏 𝑆𝑋 𝐴𝑌 𝑋𝑋 𝑤 𝑝 𝑋 𝑏 𝑆𝑋 𝐴𝑌 𝑋𝑋 𝑤 𝑝 𝑌 𝑝 𝐴 𝑤 𝑝 b 𝑆 𝐴𝑌 𝑋𝑋 𝐴 𝑋 𝑏 𝑆𝑋 ε 𝑌 𝑝 𝐴 𝑤 𝑌 Renomeando a gramática 𝐴1 𝐴4𝐴3 𝐴2𝐴2 𝐴4 𝐴2 𝑏 𝐴1𝐴2 ε 𝐴3 𝑝 𝐴4 𝑤 𝐴3 Resolver Problema 𝐴2 𝐴1𝐴2 𝐴1 𝐴4𝐴3 𝐴2𝐴2 𝐴4 𝐴2 𝑏 𝐴4𝐴3𝐴2𝐴2𝐴2𝐴2𝐴4𝐴2 ε 𝐴3 𝑝 𝐴4 𝑤 𝐴3 Resolver Problema 𝐴2 𝐴2𝐴2𝐴2 𝐴1 𝐴4𝐴3 𝐴2𝐴2 𝐴4 𝐴2 𝑏𝐵1 𝐴4𝐴3𝐴2𝐴4𝐴2 𝐵1 𝐴3 𝑝 𝐴4 𝑤 𝐴3 𝐵1 𝐴2𝐴2𝐵1𝐴2𝐴2 Resolver Problema 𝐴4 𝐴3 𝐴1 𝐴4𝐴3 𝐴2𝐴2 𝐴4 𝐴2 𝑏𝐵1 𝐴4𝐴3𝐴2𝐴4𝐴2 𝐵1 𝐴3 𝑝 𝐴4 𝑤 𝑝 𝐵1 𝐴2𝐴2𝐵1𝐴2𝐴2 Resolver Problema 𝐴1 𝐴4 e 𝐴1 𝐴4𝐴3 𝐴1 𝑤𝐴3𝑝𝐴3 𝐴2𝐴2 𝑤 𝑝 𝐴2 𝑏𝐵1 𝐴4𝐴3𝐴2𝐴4𝐴2 𝐵1 𝐴3 𝑝 𝐴4 𝑤 𝑝 𝐵1 𝐴2𝐴2𝐴2𝐴2𝐵1 Resolver Problema 𝐴2 𝐴4𝐴3𝐴2 e 𝐴2 𝐴4𝐴2 𝐴1 𝑤𝐴3𝑝𝐴3 𝐴2𝐴2 𝑤 𝑝 𝐴2 𝑏𝐵1 𝑤𝐴3𝐴2𝑝𝐴3𝐴2𝑤𝐴2𝑝𝐴2 𝐵1 𝐴3 𝑝 𝐴4 𝑤 𝑝 𝐵1 𝐴2𝐴2𝐵1𝐴2𝐴2 Resolver Problema 𝐴1 𝐴2𝐴2 e 𝐵1 𝐴2𝐴2 𝐴1 𝑤𝐴3𝑝𝐴3 𝑏𝐵1𝐴2𝑤𝐴3𝐴2𝑝𝐴3𝐴2𝑤𝐴2𝑝𝐴2 𝑤 𝑝 𝐴2 𝑏𝐵1 𝑤𝐴3𝐴2𝑝𝐴3𝐴2𝑤𝐴2𝑝𝐴2𝐵1 𝐴3 𝑝 𝐴4 𝑤 𝑝 𝐵1 𝑏𝐵1𝐴2𝑤𝐴3𝐴2𝑝𝐴3𝐴2𝑤𝐴2𝑝𝐴2𝐵1𝐴2𝐴2 Resolver Problema 𝐴2 𝐵1 𝐴1 𝑤𝐴3𝑝𝐴3 𝑏𝐵1𝐴2𝑤𝐴3𝐴2𝑝𝐴3𝐴2𝑤𝐴2𝑝𝐴2 𝑤 𝑝 𝐴2 𝑏𝐵1 𝑤𝐴3𝐴2𝑝𝐴3𝐴2𝑤𝐴2𝑝𝐴2𝑏𝐵1𝐴2𝑤𝐴3𝐴2𝑝𝐴3𝐴2𝑤𝐴2𝑝𝐴2𝐵1𝐴2𝐴2 𝐴3 𝑝 𝐴4 𝑤 𝑝 𝐵1 𝑏𝐵1𝐴2𝑤𝐴3𝐴2𝑝𝐴3𝐴2𝑤𝐴2𝑝𝐴2𝐵1𝐴2𝐴2 a S0S S AYXXA X bSXε Y p AwY Resolver problema X ε S0S S AYXXXAε X bSXS Y p AwY Resolver problema Sε S0Sε S AYXXXA X bSXS Y p AwY Resolver problema AY S0Sε S AYXXXA X bSXS Y p Awp Resolver problema X S S0Sε S AYXXXA X bSXAY XXA Y p Awp Resolver problema X A S0Sε S AYXXXA X bSXAY XXwp Y p Awp Resolver problema S A S0Sε S AYXXXwp X bSXAY XXwp Y p Awp Resolver problema S X S0Sε SbSXAYXXwp X bSXAY XXwp Y p Awp Resolver problema S0S S0bSXAYXXwpε SbSXAYXXwp X bSXAY XXwp Y p Awp b S AYXXA X bSXε Y p AwY Renomeando a gramática A1 A4 A3A2 A2A4 A2bA1 A2ε A3 p A4wA3 Resolver Problema A2 A1 A2 A1 A4 A3A2 A2A4 A2bA4 A3 A2A2 A2 A2A4 A2ε A3 p A4wA3 Resolver Problema A2 A2 A2 A2 A1 A4 A3A2 A2A4 A2bB1A4 A3 A2A4 A2B1 A3 p A4wA3 B1 A2 A2B1 A2 A2 Resolver Problema A4 A3 A1 A4 A3A2 A2A4 A2bB1A4 A3 A2A4 A2B1 A3 p A4wp B1 A2 A2B1 A2 A2 Resolver Problema A1 A4 e A1 A4 A3 A1w A3p A3A2 A2wp A2bB1A4 A3 A2A4 A2B1 A3 p A4wp B1 A2 A2A2 A2B1 Resolver Problema A2 A4 A3 A2 e A2 A4 A2 A1w A3p A3A2 A2wp A2bB1w A3 A2p A3 A2w A2p A2B1 A3 p A4wp B1 A2 A2B1 A2 A2 Resolver Problema A1 A2 A2 e B1 A2 A2 A1w A3p A3bB1 A2w A3 A2p A3 A2w A2p A2wp A2bB1w A3 A2p A3 A2w A2p A2B1 A3 p A4wp B1b B1 A2w A3 A2p A3 A2w A2p A2B1 A2 A2 Resolver Problema A2B1 A1w A3p A3bB1 A2w A3 A2p A3 A2w A2p A2wp A2bB1w A3 A2p A3 A2w A2p A2b B1 A2w A3 A2p A3 A2w A2p A2B1 A2 A2 A3 p A4wp B1b B1 A2w A3 A2p A3 A2w A2p A2B1 A2 A2