/************************************************ File: empty2.pl Author: Mihaela Malita Title: The emptiness problem. L(G) = 0 ? Method. Generate words over the alphabet with length < N ( read N). Stop at first word found. ?- start. Check if our grammar generates a^nb^n What is the maximum length of words you to test: 4. [a]Not generated [b]Not generated [a, a]Not generated [a, b]Generated!! Your grammar generates something. Good Bye **************************************************/ start:- write('Check if our grammar generates a^nb^n\n'), write('What is the maximum length of words you test: '),read(N), empty_grammar(N). /************ Our grammar in Chomsky Normal Form ************ L(G)= a^nb^n. Grammar is s --> [a],[b]. s --> [a],s,[b]. ***********************************************************/ % Same grammar but in Chomsky normal form. s --> xa,xb. xa --> [a]. xb --> [b]. s --> xa,y. y --> s,xb. % check if there is any word generated by the grammar empty_grammar(N):- generate(N,[a,b],W), nl,write(W), (phrase(s,W) -> (write('Generated!!'),bye,!) ; write('Not generated')), fail. % Cut (!) stops backtracking. bye:- nl,write('Your grammar generates something.'),write(' Good Bye'). % Generate all words with length 1 to N. generate(+N,+L,-R). generate(N,Alphabet,R):- between(1,N,K),gen(K,Alphabet,R). % Make a list with variables of length N and fill it with elements from L. gen(+N,+L,-R). gen(N,L,R):-length(R,N),mem(R,L). /* mem(-L1,+L2). Force all elements from L1 to be members of L2. ?- mem([X,Y],[a,b,c]). X = Y = a ; .. X = Y = c ; */ mem([],_). mem([H|T],L2):-member(H,L2),mem(T,L2).