MHB Determine if the string is in L(G)

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    String
AI Thread Summary
To determine if a string w is in the language of a context-free grammar G in Chomsky normal form using an O(n^3) algorithm, dynamic programming can be effectively employed. The approach involves constructing a table where for each substring of w, the set of non-terminal symbols that can derive that substring is recorded. Specifically, for every substring defined by indices i and s (where 1 ≤ i ≤ i+s ≤ n), the algorithm iteratively calculates which non-terminals can generate the substring x_i...x_{i+s}. This process is executed in a nested loop, varying the length of the substring s from 1 to n-1, allowing for a comprehensive examination of all possible substrings in the string w. This method is detailed in several computational theory texts, providing a structured framework for implementing the algorithm.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

I have to write an $O(n^3)$ algorithm to determine whether a given string $w=a_1 a_2 \dots a_n$ is in $L(G)$, where $G=(N,\Sigma ,P, S)$ is a context-free grammar in Chomsky normal form.

Could you give me some hints how to do that?? (Wondering)
 
Technology news on Phys.org
Could you explain me how we could use the dynamic programming in this case?? (Wondering)
 
This is described in Section 3.6 in [1], Theorem 7.16 in [2] and Section 7.4.4 in [3]. Briefly, the idea is the following. Given a word $x_1\dots x_n$, for each $i$ and $s$ such that $1\le i\le i+s\le n$ find the set $N[i,i+s]$ of all symbols that can derive $x_i\dots x_{i+s}$. This computation occurs in a loop where $s$ changes from 1 to $n-1$.

[1] Lewis, Papadimitriou. Elements of the Theory of Computation. 2nd edition.

[2] Sipser. Introduction to the Theory of Computation. 2nd edition.

[3] Hopcroft, Motwani, Ullman. Introduction to Automata Theory, Languages, and Computation. 2nd edition.
 
Dear Peeps I have posted a few questions about programing on this sectio of the PF forum. I want to ask you veterans how you folks learn program in assembly and about computer architecture for the x86 family. In addition to finish learning C, I am also reading the book From bits to Gates to C and Beyond. In the book, it uses the mini LC3 assembly language. I also have books on assembly programming and computer architecture. The few famous ones i have are Computer Organization and...
I have a quick questions. I am going through a book on C programming on my own. Afterwards, I plan to go through something call data structures and algorithms on my own also in C. I also need to learn C++, Matlab and for personal interest Haskell. For the two topic of data structures and algorithms, I understand there are standard ones across all programming languages. After learning it through C, what would be the biggest issue when trying to implement the same data...
Back
Top