As usual, I did mine in Groovy. Bonus builder code makes up most of the text.

package net.nubsis.animals;

import groovy.transform.Canonical

@Canonical
class Animal{
    String name
    def questions = []

    boolean test(question){
        question in questions
    }
}


// Helper class to make Animal objects
class AnimalBuilder {

    Set<String> questions = []
    Map<String, Animal> animals = [:]

    AnimalBuilder build(Closure cl){
        cl.resolveStrategy = Closure.DELEGATE_ONLY
        cl.delegate = this
        cl.call()
        return this
    }

    Animal a
    def animal(String name, Closure cl){
        a = animals[name] 

        if(!a){
            a = new Animal(name:name)
            animals[name] = a
        }
        cl.resolveStrategy = Closure.DELEGATE_ONLY
        cl.delegate = this
        cl.call()
    }

    def has(String... attributes){
        attributes.each{
            def q = "Does your animal have $it?"
            questions << q
            a.questions << q
        }
    }

    def is(String... attributes){
        attributes.each{
            def q = "Is your animal $it?"
            questions << q
            a.questions << q
        }
    }
}

// Make a couple of animals
def builder = new AnimalBuilder().build{
    animal('Dog'){
        has 'a tail', 'paws', 'fur'
        is 'domesticated', 'a mammal', 'canine'
    }
    animal('Cat'){
        has 'a tail', 'paws', 'fur'
        is 'domesticated', 'a mammal', 'feline'
    }
    animal('Whale'){
        has 'a tail', 'blowhole'
        is 'aquatic', 'a mammal'
    }
    animal('Lynx'){
        has 'a tail', 'paws', "fur"
        is 'feline', 'a mammal'
    }
}

// Prepare input
BufferedReader console = new BufferedReader(new InputStreamReader(System.in))
def readInput = { question ->
    print "$question --> "
    while(true){
        def input = console.readLine()
        if(input in ['y', 'Y', 'yes']){
            return true
        } else if(input in ['n', 'N', 'no']){
            return false
        }
        println "Silly human. Answer 'yes' or 'no' --> "
    }
}


def lose = { questions ->
    println "Fine, you win this time. What is the name of your animal?"
    def name = console.readLine()
    Animal a = builder.animals[name]
    if(!a){
        a = new Animal(name)
        builder.animals[name] = a
    }

    builder.a = a

    println "'$name'? Ugh. Very well. What is a something your animal *is*?"
    question = console.readLine()
    builder.is question
    println "And what is something your animal *has*?"
    question = console.readLine()
    builder.has question

    questions.each {
        a.questions << it
    }
    println "Alright. Thank you."
}

def play = {
    def remainingAnimals
    def remainingQuestions
    def askedQuestions
    def answers

    def reset = {
        remainingAnimals = builder.animals.values().collect()
        remainingQuestions = builder.questions.collect()
        answers = []
    }

    def askReset = {
        def moar = readInput("Do you want to play again?")
        if(moar)
            reset()
        return moar
    }

    reset()
    while(remainingAnimals){

        //println "Remaining animals: ${remainingAnimals*.name}"
        //println "Remaining questions: ${remainingQuestions.size()}"
        if (remainingAnimals.size == 1) {
            if(readInput("Is your animal ${remainingAnimals[0].name}?"))
                println "Well, that was easy."
            else
                lose(answers)
            if(!askReset())
                break
        } else if(remainingAnimals.size() > 1) {
            def counts = remainingQuestions.collect{q -> new MapEntry(q, remainingAnimals.findAll{it.test q})}.findAll{!it.value.empty}
            counts.sort{it.value.size()}.each {
                //Debug: See the questions that are considered and which animals they keep/eliminate
                // println "$it.key: ${it.value*.name}"
            }
            remainingQuestions = counts.findAll{!it.value.empty}*.key

            MapEntry q = counts.sort{it.value.size()}.find{it.value.size() >= remainingAnimals.size()/2}
            if(!q)
                q = counts.first()

            remainingQuestions.remove q.key
            if(readInput(q.key)){
                remainingAnimals = q.value
                answers << q.key
            }
            else
                remainingAnimals.removeAll q.value
        } else {
            lose(answers)
            askReset()
        }
        println()
    }

    println "Farewell, human. You have entertained me."
}

play()