/************************************************
 File: empty1.pl
 Author: Mihaela Malita
 Title:  The emptiness problem. L(G)=0 ?
 Method. Generate all words over the alphabet with length  < N ( read N).
         For each word check if your grammar generates it
            Example. ?- start.
            Check if our grammar generates a^nb^n
            What is the maximum length of words you test: 4.
            [a]-notgenerated
            [b]-notgenerated
            [a, a]-notgenerated
            [a, b]-generated
            [b, a]-notgenerated
            [b, b]-notgenerated
            [a, a, a]-notgenerated
           ...
            [a, a, b, a]-notgenerated
            [a, a, b, b]-generated
            [a, b, a, a]-notgenerated
            ...
            [b, b, b, b]-notgenerated
            
            Yes
**************************************************/ 
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):- forall(generate(N,[a,b],W),
                       (nl,phrase(s,W) -> (write(W-generated)) ; write(W-notgenerated))).
                       
% 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):-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).