Algoritmia - Ejercicio de programacion dinamica

Ejercicio de programacion dinamica

Publicado por Marcelo (1 intervención) el 25/06/2005 02:27:51

tengo q resolver este problema y no se como!
"Dada una gramática G=<N,T,P,S>:
N: alfabeto de no terminales
T: alfabeto de terminales
P: conjunto de reglas de producción
S: elemento distinguido
P:
S -> AD | DC
A -> DA | a
D -> CC | b
C -> AD | a

Construir un algoritmo utilizando la técnica de Programación Dinámica que determine si una cadena w=a1a2...an pertenece al lenguaje.
Se requiere una interfaz que permita ingresar diferentes cadenas."

por favor me podrian ayudar?

Valora esta pregunta

Me gusta: Está pregunta es útil y esta clara

No me gusta: Está pregunta no esta clara o no es útil

Responder

Verificación de pertenencia al lenguaje con programación dinámica

Publicado por Alejandro (307 intervenciones) el 05/03/2024 18:44:04

Marcelo, para determinar si una cadena w = a_1a_2...a_n pertenece al lenguaje definido por la gramática G = ⟨ N, T, P, S 〉, podemos utilizar un algoritmo basado en la técnica de programación dinámica. Aquí hay un enfoque para resolver este problema:

1. Definir la estructura de datos:
- Utiliza una matriz dp donde dp[j] representará si la subcadena w[i...j] pertenece al lenguaje.

2. Inicializar la matriz base:
- Para cada terminal a en la cadena w, inicializa dp según las reglas de producción que incluyen terminales.

3. Llenar la matriz utilizando reglas de producción:
- Utiliza las reglas de producción de la gramática para determinar si las subcadenas más largas pertenecen al lenguaje, utilizando las subcadenas más cortas ya calculadas.

4. Verificar si la cadena completa pertenece al lenguaje:
- La entrada completa [i]w pertenecerá al lenguaje si [i]dp[0][n-1] es verdadero, donde [i]n es la longitud de la cadena.

5. Implementar en código:
- Traduce el algoritmo a tu lenguaje de programación preferido y crea una interfaz para ingresar diferentes cadenas.

Ejemplo en Python:

def pertenece_al_lenguaje(w):

    n = len(w)

    dp = [[False] * n for _ in range(n)]

    # Inicialización para terminales

    for i in range(n):

        if w[i] == 'a' or w[i] == 'b':

            dp[i][i] = True

    # Llenar la matriz utilizando reglas de producción

    for length in range(2, n + 1):

        for i in range(n - length + 1):

            j = i + length - 1

            for k in range(i, j):

                # Reglas de producción de la gramática

                if (dp[i][k] and dp[k + 1][j]) or (dp[i][j] or (w[i] == 'a' and w[j] == 'b')):

                    dp[i][j] = True

    # La cadena completa pertenece al lenguaje si dp[0][n-1] es verdadero

    return dp[0][n - 1]

# Ejemplo de uso

cadena = input("Ingrese la cadena a verificar: ")

if pertenece_al_lenguaje(cadena):

    print("La cadena pertenece al lenguaje.")

else:

    print("La cadena no pertenece al lenguaje.")

Este código utiliza la técnica de programación dinámica para determinar la pertenencia de una cadena al lenguaje definido por la gramática proporcionada. Puedes ingresar diferentes cadenas para verificar su pertenencia al lenguaje.

Valora esta respuesta

Me gusta: Está respuesta es útil y esta clara

No me gusta: Está respuesta no esta clara o no es útil

Comentar